백준 2504 괄호의 값

답

lines = input()

stack = [] # 괄호를 관리하는 스택
tmp = 1 # 계산된 수를 관리하는 스택 (push -> *, pop -> //)
res = 0 # 정답

for i in range(len(lines)):
    if lines[i] == "(":
        stack.append("(") # 여는 괄호들은 스택에 push.
        tmp *= 2 # 숫자는 push가 곱셈
    elif lines[i] == "[":
        stack.append("[")
        tmp *= 3
    elif lines[i] == ")":
        if not stack or stack[-1] == "[": # 스택이 비어있는데 닫으면 잘못된 경우임, 마찬가지로 여는 괄호가 다르면 잘못된 경우임
            res = 0
            break
        elif lines[i - 1] == "(": #곱셈 종료 시점 트리거 여기부터 나오는 닫는 괄호들은 pop만 해줄 뿐
            res += tmp
        stack.pop()
        tmp //= 2
    elif lines[i] == "]":
        if not stack or stack[-1] == "(": # 스택이 비어있는데 닫으면 잘못된 경우임, 마찬가지로 여는 괄호가 다르면 잘못된 경우임
            res = 0
            break
        elif lines[i - 1] == "[": #곱셈 종료 시점 트리거 여기부터 나오는 닫는 괄호들은 pop만 해줄 뿐
            res += tmp
        stack.pop()
        tmp //= 3

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

생각

진짜 엄청 헤맸다. 감 잊지 않도록 내일도 다시 풀어볼 예정이다.
풀다풀다 모르겠어서 검색을 해봤으나, 나누기 2와 나누기 3을 하는게 이해가 안됐다 도대체 와이?
주변에 코테 잘 푸는 형한테 물어보고, 진짜 명쾌한 해답을 알았다.
계산식 분해하듯이 풀어보면 답이 보인다는 것이었다!

가령 (()[[]])([]) 일때 이를 단계별로 풀어보면
2 ( 2 + 3 3 ) + 2 3
2 2 + 2 3 3 + 2 * 3

이걸 예쁘게 묶어보면

[2 * 2] + [2 * 3 * 3] + [2 * 3]

이렇게 된다

결국 닫는 괄호를 만났을 때, 스택에서 여는 괄호를 pop 해주는 것처럼, 숫자도 똑같이 2혹은 3을 pop해준다고 생각하니까 이해하기가 쉬워졌다!!!!

즉, 두개의 스택이 있다고 생각하고... 괄호를 관리하는 스택은 stack에, 계산한 값을 관리하는 스택은 tmp에 담는다고 생각하면 된다.

그래서

1. 여는 소괄호 -> tmp에 2 곱해줌
2. 여는 대괄호 -> tmp에 3 곱해줌
3. 닫는 소괄호
   a. 이전에 값이 여는 소괄호 -> stack에서 여는 소괄호 없애고, tmp에도 2를 나눠줌 (곱하기로 스택을 쌓았으니, 나누기로 스택을 없앰)
   b. 이전에 값이 여는 대괄호 -> 망한거니까 그냥 0 넣고 끝냄
4. 여는 대괄호
   a. 이전에 값이 여는 소괄호 -> 망한거니까 그냥 0 넣고 끝냄
   b. 이전에 값이 여는 대괄호 -> stack에서 여는 대괄호를 없애고, tmp에도 3을 나눠줌 (마찬가지)

근데 이제 자꾸 틀려서 마지막에 인터넷을 한 번 더 본게,
끝까지 갔음에도 괄호가 남아있는 경우..! 였다
그래서 마지막에 스택에 괄호가 남아있는지 검사하고, 짝을 못찾은 괄호가 남아있는 경우에도 망한거니까 0을 반환하도록했다.

험난한 여정 끝에 성공..!!
내일 아침에 다시 풀어봐야지