[백준] 2504 파이썬(python) : 괄호의 값 - (★)

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

2504번: 괄호의 값

 

 

 

여는 괄호는 받을 때는 스택에 삽입과 함께 그 값을 저장, 첫번째 닫는 괄호가 나오면 이제까지의 값 모두 res에 옮김 그리고 괄호값만큼 나눠준다.

 

 

( ( ) [ [ ] ] ) 일때 값의 변화

괄호	(	(	)	[	[	]	]	)
tmp	2	4	2	6	18	6	2	1
res	0	0	4	4	4	22	22	22

 

 

닫는 괄호 ) 가 나왔을 때

 

 

if len(stack) == 0 or stack[-1] != '(' 여기서 안걸린다면 여는 괄호 (과 [만이 stack에 들어갈 수 있으므로 stack[-1]은 무조건 '(' 뿐이다.

 

 

그리고 올바른 괄호열이라면 앞에 여는 괄호 없이 닫는 괄호만 올 수 없다. if len(stack) == 0 or stack[-1] != '(' 여기서 stack에 들어있는 원소가 없어서 걸리게 된다.

 

 

마지막으로 닫는 괄호가 나올 때 string[i-1]에서 (가 나오지 않아 짝을 이루지 않아도 stack[-1]에서는 짝을 이뤘으니까( [가 나올 일은 없으니까) 떨어져있는 괄호로써 닫히게 된다. 그래서 tmp값만 나눠서 열리기 전 상태의 값으로 돌려준다.

 

 

import sys
string = sys.stdin.readline().rstrip()
stack = []
tmp, res = 1, 0
for i in range(len(string)):
    if string[i] == '(': #1
        stack.append(string[i])
        tmp *= 2
    elif string[i] == '[': #2
        tmp *= 3
        stack.append(string[i])
    elif string[i] == ')': #3
        if len(stack) == 0 or stack[-1] != '(': #4
            res = 0
            break
        elif string[i-1] == '(': #5
            res += tmp
        tmp //= 2 #6
        stack.pop()
    elif string[i] == ']': #7
        if len(stack) == 0 or stack[-1] != '[': #8
            res = 0
            break
        if string[i-1] == '[': #9
            res += tmp
        tmp //= 3 #10
        stack.pop()
if len(stack) != 0:
    res = 0
print(res)

 

 

tmp와 res가 0, 1인 이유는 tmp는 곱하기 과정만 수행하고 res는 더하기 과정만 수행할것이기 때문에

 

 

#1 : 입력값이 여는 괄호 (일때는 stack에 저장하고 괄호값 2만큼 tmp에 곱

#2 : 입력값이 여는 괄호 [일때는 stack에 저장하고 괄호값 3만큼 tmp에 곱

#3 : 닫힌 문자 )가 나왔을 때는 

#4 : stack의 길이가 0이거나 stack의 top이 (가 아니면 res = 0으로 하고 반복문 탈출

#5 : 직전 문자와 짝을 이룬다면 res에 tmp값을 더해준다.

#6 : ( ( ) [ [ ] ] ) 의 마지막에 위치한 닫는 괄호처럼 직전 문자와 짝을 이루지 않는 경우는 stack[-1]에서 짝을 맞췄기 때문에 닫힌 상태가 되므로 tmp만 값만큼 나눠준다.

#7, 8, 9, 10 : #3, 4, 5, 6 과 과정이 같다.

 

 

https://hgk5722.tistory.com/48

[백준] 10799 파이썬(python) : 쇠막대기 - (★)

 

 

비슷한 문제가 있어서 추가합니다.

https://hgk5722.tistory.com/260

[백준] 12789 파이썬(python) : 도키도키 간식드리미 - (올바른배열인지확인)