[백준] 2504 괄호의 값 - Python

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

2504번: 괄호의 값

몇달 전에 풀어본 문제였지만, 역시나 풀어봤던 기억만 날 뿐 풀이는 기억나지 않았다. stack을 이용하여 푼다는 것은 알고 있었지만, 값을 계산하는 데에서 시간이 오래 걸렸다.

다른 블로그의 글과는 달리 코드가 길어졌지만, 93%에서 틀리고 스스로 반례를 찾아서 문제를 해결한 것에 의의를 두도록 한다.

 

풀이

from collections import deque

q = list(input())
deq = deque()

answer = 0
status = True
for i in range(len(q)) :
    # 열린 괄호의 경우 무조건 push
    if q[i] == '(' or q[i] == '[' :
        deq.append(q[i])
        continue
    
    if not deq :
        answer = -1
        break
    
    # stack이 비어있지 않은 상태에서 닫는 괄호가 들어왔을 때
    if q[i] == ')' :
        temp = 0
        while deq  :
            idx = len(deq)-1
            if deq[idx] == '[' :
                # 비정상
                answer=-1
                status = False
                break
            elif deq[idx] == '(' :
                deq.pop()
                break
            # 숫자라면
            if len(deq) < 2:
                # 비정상 (deq에 숫자만 남은 경우)
                answer=-1
                status = False
                break
            temp += deq[idx]
            deq.pop()
        deq.append(2 if temp == 0 else 2*temp)
    elif q[i] == ']' :
        temp = 0
        while deq :
            idx = len(deq)-1
            if deq[idx] == '(' :
                # 비정상
                answer=-1
                status = False
                break
            elif deq[idx] == '[' :
                deq.pop()
                break
            # 숫자라면
            if len(deq) < 2:
                # 비정상 (deq에 숫자만 남은 경우)
                answer=-1
                status = False
                break
            temp += deq[idx]
            deq.pop()
        deq.append(3 if temp == 0 else 3*temp)
    if not status :
        break
    
if answer == -1 :
    print(0)
else :
    while deq : 
        if deq[-1] == '(' or deq[-1] == '[' or deq[-1] == ')' or deq[-1] == ']' :
            answer = 0
            break
        answer += deq.pop()
    print(answer)

다른 사람들의 풀이

from collections import deque

q = list(input())
deq = deque()

answer = 0
temp = 1
status = True

for i in range(len(q)) :
    if q[i] == '(' :
        deq.append(q[i])
        temp *= 2
    elif q[i] == '[' :
        deq.append(q[i])
        temp *= 3
    # 불가능한 경우
    elif q[i] == ')' and (not deq or deq[-1] == '[') :
        answer = 0
        status = False
        break
    elif q[i] == ']' and (not deq or deq[-1] == '(') :
        answer = 0
        status = False
        break
    # 가능한 경우
    elif q[i] == ')' :
        if q[i-1] == '(' :
            answer += temp
        deq.pop()
        temp //= 2
    elif q[i] == ']' :
        if q[i-1] == '[' :
            answer += temp
        deq.pop()
        temp //= 3
    
if not status or deq :
    print(0)
else :
    print(answer)

해당 코드를 살펴보니, 분배법칙을 이용하였다. 괄호 특성상 2*(2+3*3) = 2*2+2*3*3으로 표현될 수 있는데, temp가 해당 분배법칙의 항을 나타내는 것이고, answer는 괄호가 닫힐 때 input값의 이전 괄호와 비교했을 때 내부에 다른 괄호가 없는지 확인한 뒤 result에 더하는 것이다.

즉, 계속 temp에 분배법칙을 적용하여 계산한 뒤, 마지막 내부의 괄호의 경우에 result에 더해준다.