[Algorithm] 백준 2504 : 괄호의 값

문제
https://www.acmicpc.net/problem/2504
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Gold/2504.%E2%80%85%EA%B4%84%ED%98%B8%EC%9D%98%E2%80%85%EA%B0%92/%EA%B4%84%ED%98%B8%EC%9D%98%E2%80%85%EA%B0%92.py

괄호 문제라는 것을 읽는 순간 스택을 사용해야겠다고 생각했다. 스택을 사용해서 문제를 풀어야 하는데, 그 괄호에 따라 수 연산을 해야한다고 하니 좀 복잡했다. 특히 어떤 상황에서 곱하는 연산을 하고 더하는 연산을 해야하는 지 판단하는 데에 시간이 걸렸다.

여는 괄호 나오면 괄호를 stack에 넣어준다. 닫는 괄호가 나오면 여러가지 상황을 나누어서 판단해야했다. 우선 stack이 비어있으면 제대로 된 괄호 상태가 아니다. 만약 비어있지 않은 경우에는 스택에서 pop한 값에 따라 하는 행동이 달라진다. 만약 짝이 맞지 않은 괄호가 pop 된다면 제대로된 괄호 상태가 아니다. 다음으로 숫자가 pop이 된다면 해당 값을 쭉 더해준다. 짝이 맞는 괄호가 pop 되면 sum의 상태에 따라 각각 다른 연산을 하여 stack에 추가해준다.

스택에 숫자가 연속으로 들어있는 경우에는 그 숫자들을 계속해서 더해주고(더하기 연산), 올바른 괄호 짝을 맞췄을 때는 곱하기 연산을 한다.

위와 같은 방식으로 괄호 문자열 연산을 마치고 stack의 상태를 본다. 만약 stack에 괄호들이 남아있다면 이는 제대로 된 괄호 상태가 아니고, stack 속에 숫자들만 남아있다면 그 값들을 모두 더해주고 (숫자가 연속으로 들어있는 경우 - 더하기 연산) 결과 값을 출력한다.

해당 코드를 구현하면서 실수를 많이했고 다 풀었다고 생각했지만 판단하지 못한 상황들이 계속해서 나와서 생각보다 어려웠던 것 같다. 오류를 찾아내기 위해 디버깅해 보았는데, 금방 어디서 오류가 발생했는 지 알 수 있었다.

< 풀이 코드 >

import sys
input = sys.stdin.readline

string = input()
stack = []
state = True

for s in string:
    if state:
        sum = 0
        if s == '(':
            stack.append('(')
        elif s == ')':
            while True:
                if len(stack) == 0:
                    state = False
                    break
                else:
                    p = stack.pop()
                    if p == '(':
                        if sum == 0:
                            stack.append('2')
                        else:
                            stack.append(str(sum*2))
                        break
                    elif p == ')' or p == '[' or p == ']':
                        state = False
                        break 
                    else:
                        sum += int(p)
        elif s == '[':
            stack.append('[')
        elif s == ']':
            while True:
                if len(stack) == 0:
                    state = False
                    break
                else:
                    p = stack.pop()
                    if p == '[':
                        if sum == 0:
                            stack.append('3')
                        else:
                            stack.append(str(sum*3))
                        break
                    elif p == ']' or p == '(' or p == ')':
                        state = False
                        break 
                    else:
                        sum += int(p)
    else:
        break

result = 0
for s in stack:
    if s == '(' or s == ')' or s == '[' or s == ']':
        state = False
        break
    else:
        result += int(s)

if state:
    print(result)
else:
    print(0)