[파이썬] [스택] 백준 2504 괄호의 값

문제

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

2504번: 괄호의 값

 

코드

array=list(input())

stack=[]
temp=1
result=0

for i in range(len(array)):
    if array[i]=="(":
        stack.append("(")
        temp*=2
    elif array[i]=="[":
        stack.append("[")
        temp*=3
    elif array[i]==")":
        if not stack or stack[-1]=="[":
            result=0
            break
        if array[i-1]=="(":
            result+=temp
        stack.pop()
        temp//=2
    else:
        if not stack or stack[-1]=="(":
            result=0
            break
        if array[i-1]=="[":
            result+=temp
        stack.pop()
        temp//=3
        
if stack:
    print(0)
else:
    print(result)

생각 정리

열린 괄호를 만나면 스택에 넣어주고 닫힌 괄호를 만나면 스택의 TOP을 꺼내 쌍을 맞춰주자.
이 때, 쌍이 맞지 않으면 잘못된 괄호 입력이다.

'( ( [ ] ) )' 라는 입력이 들어왔다면,
스택에 ' ( ( [ ' 가 있는 상태로 ]를 만나 스택의 TOP인 '['를 꺼내 쌍을 이루고
다음으로 ')'를 만나 TOP인 '('를 꺼내 쌍을 이루기 때문에 올바른 쌍을 이룬다.

하지만 '( [ ) ]' 라는 입력이 들어왔다면,
스택에 ' ( [ '가 있는 상태로 ')'를 만나 스택의 TOP인 '['를 꺼낸다면
'['와 ')'은 쌍을 이루지 않기 때문에 잘못된 입력이므로 0을 출력한다.

그리고 '( )' 소괄호의 값은 2이며 '[ ]' 대괄호의 값은 3이고
괄호 안에 또 괄호가 존재하면 값을 곱해나가는 방식이다.

그래서 '(' 괄호가 열리면 2를 곱해주고 '[' 괄호가 열리면 3을 곱해준다.
그리고 괄호를 닫은 경우는 계산한 값을 저장한 후에 누적 계산은 다시 나누기 2나 3을 해주어 원래대로 값을 돌린다.

한 가지 주의해야 할 점은 꺼낸 괄호가 닫는 괄호일 때,
괄호 입력 배열에서의 그 괄호의 바로 직전의 괄호가 쌍이 맞는 경우에만 곱하기를 한다.

즉, ' [ ( ) ] ' 처럼 마지막 ' ] ' 의 바로 직전의 괄호가 ' [ ' 가 아닌 ' ) ' 이기 때문에
값을 더해가지 않는다.

여기서 우리가 계산해야 할 것은 3 x 2 = 6인데
앞에서 곱하기 3은 이미 계산을 했기 때문에 뒤에서 더 계산을 하면 안되기 때문이다.