[Baekjoon] 2504번 : 괄호의 값 (Python, 구현, 스택)

[Baekjoon] 2504번 : 괄호의 값 (Python, 구현, 스택)

 

목차

 

 

 

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

2504번: 괄호의 값

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 76ms / 코드 길이 622B

 

문제를 풀기 이전에 본 문제의 특성을 이해할 필요가 있다.

 

()는 2를 곱하고 []는 3을 곱한다.

이를 중첩으로 쌓으면 (()) = 2*2, ([]) =  2*3, ([()]) = 2*3*2이고 (()[[]]) = (2 + 3*3) = 2*2 + 2*3*3이 가능함을 알 수 있다.

 

즉, 말하고자 하는 바는 '('나 '['의 시작 개수에 따라 그 곱이 정해지고 이를 닫을 때 그 상황에 맞게 별도의 숫자 계산이 가능하다는 것이다.

 

우리는 본 문제에서 tmp라는 중간 계산 역할을 하는 것을 통해 이를 가능하게 할 것임을 보이고자 한다.

 

(()[[]])를 활용하여 아래 본 코드를 이해해보자. 

초기 tmp=1, ans=0이라 설정한다.

 

 

 

(()[[]])	tmp = 1	ans = 0
(	*2 = 4	0
((	*2 = 4	0
(()	//2 = 2 => '('가 닫히므로 이에 대한 계산이 끝나기 때문에 2를 나눠준다.	4
(()[	*3 = 6	4
(()[[	*3 = 18	4
(()[[]	//3 = 6 => '['가 닫히므로 이에 대한 계산이 끝나기 때문에 3를 나눠준다	4+18=22
(()[[]]	//3 = 2 => '['가 닫히므로 이에 대한 계산이 끝나기 때문에 3를 나눠준다	22
(()[[]])	//2 = 1 => '('가 닫히므로 이에 대한 계산이 끝나기 때문에 2를 나눠준다	22

 

만약 정상적인 괄호 조합이라면 tmp=1에서 시작해서 1로 마무리될 것이고 정답은 조합에 맞게 뽑힐 것이다.

만약 비정상적인 괄호 조합이라면 스택에 담긴 각 괄호별 조건에 따라 걸러질 것이다.

 

 

s = list(input())
stack = []
ans = 0
tmp = 1

for i in range(len(s)):
    if s[i] == '(':
        stack.append(s[i])
        tmp *= 2
    elif s[i] == '[':
        stack.append(s[i])
        tmp *= 3
    elif s[i] == ')':
        if not stack or stack[-1] == '[':
            ans = 0
            break
        if s[i-1] == '(':
            ans += tmp
        stack.pop()
        tmp //= 2
    elif s[i] == ']':
        if not stack or stack[-1] == '(':
            ans = 0
            break
        if s[i-1] == '[':
            ans += tmp
        stack.pop()
        tmp //= 3

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