[백준][boj]괄호의 값 (Python) - 스택의 응용

문제파악

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

 

 

 

---

 

 

 

접근 방법

스택의 기본문제인 괄호 문제는 많이 풀어보았지만, 조금만 응용이 들어가니 어렵게 느껴졌다.

이 문제에서의 중요한 점은 (X) 형태는 곱해주어야하고(종속), XY 형태라면 더해주어야 한다는 것이였다 ! 

입력 예제 :
( ( ) [ [ ] ] )  ( [ ] )

 

위의 예제로 보았을 때, 우리는 ( ( ) [ [ ] ] ) 와 ( [ ] ) 값을 더해주어야한다는 것을 한 눈에 알아볼 수 있다.

그러면, 종속은 어떻게 확인할 수 있을까 ?

 

만일 우리가 ( ( ) ) 라는 괄호가 종속인 것을 판단하는 방법을 생각해보자. (전제 올바른 괄호)

가장 내부의 한쌍이 나타났을 때, 그 후 뒤는 괄호가 종료되는 것이 아닌가 ?

 

( ( ) ) [ ] -> 가장 내부 이후부터는 올바른 괄호라면 정상적으로 ( ( ) ) 종속 형태가 모두 계산되고,

 그후 뒤에 있는 [ ] 괄호는 따로 계산하여 더해주면 된다 ! 

 

코드로 알아보자

 

 

---

 

 

코드 구현

# 괄호의 값

arr = input()
stack = []

answer = 0 
temp = 1

for i in range(len(arr)):
	# 열린 괄호를 스택으로 넘겨주며, 계산해준다.
    if(arr[i]=='('):
        stack.append(arr[i])
        temp*=2
    elif(arr[i]=='['):
        stack.append(arr[i])
        temp*=3
    elif(arr[i]==')'):
    	# 만약, 닫힌 괄호가 들어왔을 때 스택이 비어있거나 스택의 마지막 값이 올바른 짝이 아니면 올바른 괄호가 아니다.
        if not stack or stack[-1] =='[':
            answer = 0
            break
        # 가장 내부의 괄호가 나왔다면 답을 더해준다.
        if arr[i-1] =='(':
            answer += temp
        # 임시 값을 초기화 해가며 알맞은 쌍의 괄호들을 지워준다.
        stack.pop()
        temp //= 2
    else:
        if not stack or stack[-1] == '(':
            answer =0
            break
        if arr[i-1] == '[':
            answer += temp
        stack.pop()
        temp //= 3

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