[백준2405/골드5] 괄호의 값 - Python

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

 

 

문제 처음 보고 어떻게 괄호의 값 계산할지 엄청 고민했다.

1. 괄호 하나씩 순회할때마다 전위표시법으로 바꿔서 나중에 계산하기, 2. 괄호 하나씩 나올 때마다 해당하는 숫자 (2 또는 3) 따로 저장해준 뒤 적절할 때에 최종 값에 반영하기, 3. 괄호가 닫힐때만 스택에서 이전 값 제거하면서 최종 값에 반영하기 까지 생각 해봤다.

 

고민해본 결과 핵심은 괄호 문자열 하나씩 순회할때마다 그 값을 저장하고 더하기가 나올 때마다 갱신해주는 거라고 생각했다.

그럼 이제 언제 값을 임시로 저장해주고 더하기가 나올때마다 최종 값에 반영할 수 있지 생각해봤다. 괄호를 전부 숫자로 변경하면서 그려봤는데 분배법칙을 이용해서 풀면 되겠다는 생각이 들었다.

 

 

1. 열린 괄호가 들어오면 무조건 스택에 추가하고 temp에 저장

2-1. 닫힌 괄호가 들어왔을 때 스택이 비어있으면 break

2-2. 닫힌 괄호가 들어왔을 때 i-1과 짝이 안맞으면 break ( ex. ( ] 또는 [ ) )

3-1. 닫힌 괄호가 들어왔을 때 i-1과 짝이 맞으면 그떄 최종 결과에 추가하고 열린 괄호 pop ( + 계산 진행 )

3-2. 닫힌 괄호가 들어왔을 때 i-1이 닫힌 괄호이면 이미 앞에서 계산해주고 pop 했으므로 그거와 맞는 괄호 다시 pop

4. for 문 전부 순회하고 stack에 괄호가 남아있으면 올바르지 못한 괄호

 

# 성공 코드

string = input()

stack = []
total = 0
temp = 1
open = {'(':2, '[':3}
close = {')':2, ']':3}

for i in range(len(string)):

    cur = string[i]

    # 1. 열린 괄호가 들어오면 무조건 스택에 추가하고 temp에 저장
    if cur in open:
        stack.append(cur)
        temp *= open[cur]

    elif cur in close:

        # 2-1. 닫힌 괄호가 들어왔을 때 스택이 비어있으면 break
        if not stack:
            total = 0
            break

        # 2-2. 닫힌 괄호가 들어왔을 때 i-1과 짝이 안맞으면 break ( ex. ( ] 또는 [ ) )
        elif stack[-1] in open and open[stack[-1]] != close[cur]:
            total = 0
            break

        # 3-1. 닫힌 괄호가 들어왔을 때 i-1과 짝이 맞으면 그떄 최종 결과에 추가하고 열린 괄호 pop ( + 계산 진행 )
        elif stack[-1] in open and string[i-1] == stack[-1]:
            total += temp

        # 3-2. 닫힌 괄호가 들어왔을 때 i-1이 닫힌 괄호이면 이미 앞에서 계산해주고 pop 했으므로 그거와 맞는 괄호 다시 pop
        stack.pop()
        temp //= close[cur]

# 4. for 문 전부 순회하고 stack에 괄호가 남아있으면 올바르지 못한 괄호
if stack:
    total = 0

print(total)

 

괄호 값 계산하느라 그림 엄청 많이 그려봤다. 생각해내느라 며칠 걸리고 머리 터질거같았다.

아직은 자료구조 중에 스택이 제일 어려운 거 같다.