골드 5 괄호의 값

문제: 골드 5 괄호의 값

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

 

풀이코드

# (): 2, []: 3
# ()() = 2+2
# (()) = 2*2
# 스택 안에 차례대로 넣는데...
# -> ( 다음에 뱌로 )가 나오면 숫자
# -> ( 안에 뭔가 있으면.. * 

S = input().rstrip('\n')
stack = []
ans = 0
tmp = 1
prev = ''

for s in S: 
    if s == '(': 
        stack.append(s)
        tmp *= 2
    elif s == '[': 
        stack.append(s)
        tmp *= 3
    elif s == ')': 
        if not stack or stack[-1] != '(': 
            ans = 0
            break
        if prev == '(': ans += tmp
        stack.pop()
        tmp //= 2
    elif s == ']': 
        if not stack or stack[-1] != '[': 
            ans = 0
            break
        if prev == '[': ans += tmp
        stack.pop()
        tmp //= 3
    prev = s
else: 
    if stack: ans = 0
    
print(ans)

 

---

느낀 점

더 문제를 많이 풀어봐야겠다.. 좀만 변형이 나와도 어려운 걸 보니 아직 많이 안 풀어봐서 그런 것 같다.

 

일단 해당 문제는 총 두 가지 풀어야 할 점이 있다. 

1. 올바른 괄호열인지 확인하는 것

2. 괄호에 따라 연산을 진행하는 것

 

일단 스택을 만들어서 무조건 ( 나 [ 면 넣어주었다. 이때 tmp를 만들어서 tmp엔 괄호에 해당하는 값을 곱해주었다. 

for s in S: 
    if s == '(': 
        stack.append(s)
        tmp *= 2
    elif s == '[': 
        stack.append(s)
        tmp *= 3

그리고 )일 경우 올바른 괄호가 되지 않는 경우를 생각해보았다. 

만약 스택에 아무것도 없는데 )가 들어오는 경우와 스택의 top에 (가 없는데 )가 들어오면 맞지 않은 괄호인 경우였다. 때문에 이때 ans를 0으로 만들어주고 for문을 바로 break 해주었다. 

만약 올바른 괄호라면 이전이 (인지 확인하고 ans에 tmp를 더해주어야 한다. 왜냐하면 이전이 (인 경우는 ()가 되기 때문에 지금까지 곱해져있던 tmp가 그냥 그 값이 되기 때문에 바로 ans에 tmp를 더해주어야 한다. 왜일까? 반대의 경우를 생각해보면 이전이 (가 아닌 경우 (...) 처럼 괄호 안에 이미 값이 있는 상태이다. 

예를 들어 (())를 생각해보면...
안쪽 ()에서 이미 값을 더했고, 바깥 )는 그 값을 단순히 감싸는 역할(곱셈)
-> 즉 바깥 )에서 또 더해버리면 값이 중복 계산됨

 

그리고 괄호를 닫았다는 것은 해당 괄호의 범위가 끝났다는 뜻이므로, 괄호를 열 때 곱해준 값을 원래대로 되돌리기 위해 tmp를 나눠준다.

• )를 닫으면 tmp //= 2
• ]를 닫으면 tmp //= 3

마지막으로 모든 문자를 처리한 뒤에도 스택이 남아있다면 여는 괄호가 닫히지 않은 것이므로 올바른 괄호열이 아니어서 ans = 0을 출력한다.

 

사실 이 문제는 GPT의 도움을 좀 많이 받았다. 

나는 처음엔 (나 [가 들어올 때 바로 곱해주거나 tmp를 따로 두지 ㅇ낳았는데 그렇게 진행하니 도저히 안 풀렸다. 

때문에 일일이 예시를 들어 이해했다. 

예시: (()[[]])([])

## 시작
stack = []
tmp = 1
ans = 0
prev = ''

# ----- 첫 번째: (
stack = ['(']
tmp = 1 * 2 = 2
ans = 0
prev = '('
# ----- 두 번째: (
stack = ['(', '(']
tmp = 2 * 2 = 4
ans = 0
prev = '('
# ----- 세 번째: )
이전 문자 = '(' 였기 때문에 () 완성!
ans += tmp → ans += 4 → ans = 4
stack.pop() → ['(']
tmp //= 2 → tmp = 2  # 괄호 하나를 나왔으니까 //2 해주어야 함
prev = ')'
# ----- 네 번째: [
stack = ['(', '[', '[']
tmp = 6 * 3 = 18
prev = '['
# ----- 다섯 번째: ]
이전 문자 = '[' 였기 때문에 [] 완성!
ans += tmp → ans += 18 → ans = 22
stack.pop() → ['(', '[']
tmp //= 3 → tmp = 6
prev = ']'

...

 

비슷한 문제를 좀 더 풀어보고 다양한 유형에 좀 더 익숙해질 때까지 문제를 더 풀어봐야겠다.