[백준 구현] 2504 괄호의 값

🥕 [ 백준 2504 ] 괄호의 값

문제 링크

url : https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

🍒 문제 분석

( ) 는 2, [ ] 는 3 이다. 서로 병렬 관계일 때는 +, 겹쳐있을 때는 * 연산을 한다.

가령 ' ( ( ) [ [ ] ] ) ( [ ] ) ' 가 있으면, 2 * (2 + 3*3) + 2*3 으로 나타낼 수 있다.

 

 

🥑 코드

import sys
print = sys.stdout.write
input = sys.stdin.readline
s = input().rstrip()

temp = 1
ans = 0
stack = []

for i in range(len(s)):
    if s[i] == '(':
        stack.append('(')
        temp *= 2
    elif s[i] == '[':
        stack.append('[')
        temp *= 3
    elif s[i] == ')':
        if not stack or stack[-1] == '[' :   # (, ), ] 면 통과
            ans = 0
            break
        if stack[-1] == '(':                 # ), ] 면 여기에 해당 안되지만, stack에 그걸 넣은적은 없음.
            stack.pop()
            if s[i-1] != ')' and s[i-1] != ']':  # 이전께 ( 또는 [ 면 ans에 더함
                ans += temp
            temp //= 2
    elif s[i] == ']': 
        if not stack or stack[-1] == '(' :
            ans = 0
            break
        if stack[-1] == '[':
            stack.pop()
            if s[i-1] != ')' and s[i-1] != ']':
                ans += temp
            temp //= 3

print(str(ans))

틀렸다고 뜨는데 왜 틀렸는지 모르겠다.

 

#input

(()

다음의 예외 사항으로 인해 틀린거였다.

 

if stack : print(0)
else : print(answer)

마지막에 스택이 비었는지 안비었는지 코드만 넣어주면 끝난다.

 

🍓 내 해결 과정

문제를 처음 접했을 때, 스택이라는 자료구조는 떠올렸지만 이와 별개로 문제를 풀 수는 없었다.

스터디 팀원 분이 분배 법칙으로 문제를 접근하는걸 설명해주셔서 이에 아이디어를 얻어 나도 그렇게 풀어보고자 했다.

 

 

🌽 다른 사람 코드

s = input()
strings = []
answer = 0
tmp = 1

for i in range(len(s)):
    if s[i] == '(':
        strings.append(s[i])
        tmp *= 2
    elif s[i] == '[':
        strings.append(s[i])
        tmp *= 3
    elif s[i] == ')':
        if not strings or strings[-1] == '[':
            answer = 0
            break
        if s[i-1] == '(':
            answer += tmp
        tmp //= 2
        strings.pop()
    else:
        if not strings or strings[-1] == '(':
            answer = 0
            break
        if s[i-1] == '[':
            answer += tmp
        tmp //= 3
        strings.pop()

if strings: print(0)
else: print(answer)

 

 

🍉 깨달은 점 및 정리

1. 분배법칙으로 계산할 때,

tmp라는 변수를 둬서, 괄호 안에 들어갈 때마다 곱하고, 괄호 밖에 나올때 마다 나눠서

ans에 필요할 때 더한다는 아이디어

 

2. 스택 활용

 

3. 드디어 내 코드가 왜 틀렸었는지 알았다.

앞으로 저런 스택 문제를 풀 때, 항상 마무리에 스택 안에 값이 남아있는지 안남아있는지를 확인하도록 하자!