BOJ 2504 - 괄호의 값

풀이

---

처음엔 replace 를 이용해야하나 싶었으나 다른분들의 풀이를 보고 스택을 활용한 구현문제였다는 것을 알 수 있었다.

간단한 예시를 들어보자.

s = (()[[]])([]) 이라고 주어졌을때,

stack은 아래와 같이 생성된다.

['(']
['(', '(']
['(', 2]
['(', 2, '[']
['(', 2, '[', '[']
['(', 2, '[', 3]
['(', 2, 9]
[22]
[22, '(']
[22, '(', '[']
[22, '(', 3]
[22, 6]

여기서 알아야 할 점은 주어진 문자열을 순서대로 리스트에 옮겨담으면서 괄호가 완성될 때 마다 조건문을 통해서 정수 부여 및 연산을 실시하면된다.

3번째 iteration 의 경우, 소괄호가 완성된 시점이다. 완성된 소괄호 사이에 정수가 없으므로 2 를 스택에 삽입하고 다음 반복으로 넘어간다.

6, 7번째 iteration 의 경우, 대괄호가 완성된 시점이다. 6번째 반복의 경우 완성된 대괄호 사이에 정수가 없으므로 3 를 스택에 삽입한다. 7번째 반복의 경우 현재 스택은 ['(', 2, '[', 3] 이다. 때문에 t 는 3 이 되고 9 가 스택에 삽입된다.

위와 같은 모든 연산을 마치면 [22, 6] 이라는 리스트가 완성되고, 리스트의 sum 을 구해주면 정답이다.

하지만 짝을 이루지 못한 괄호들이 남아있을 경우를 대비해 조건문을 통해 구별해주면된다.

소스코드

---

import sys
 
input = sys.stdin.readline
 
s = input().rstrip()
stack = []
ans = 0
 
for i in s:
    if i == ")":
        t = 0
        while len(stack) != 0:
            top = stack.pop()
            if top == "(":
                if t == 0:
                    stack.append(2)
                else:
                    stack.append(2*t)
                break
            elif top == "[":
                print(0)
                exit(0)
            else:
                t += top
    elif i == "]":
        t = 0
        while len(stack) != 0:
            top = stack.pop()
            if top == "[":
                if t == 0:
                    stack.append(3)
                else:
                    stack.append(3*t)
                break
            elif top == "(":
                print(0)
                exit(0)
            else:
                t += top
    else:
        stack.append(i)
 
for i in stack:
    if i == "(" or i == "[":
        print(0)
        exit(0)
    else:
        ans += i
 
print(ans)

References

---

• BOJ 2504 - 괄호의 값