[BOJ - 자료구조] 2504번 : 괄호의 값 ( python )

자료 구조 + 스택 문제인듯 하다.

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

2504번: 괄호의 값

 

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

 

---

 

1. 이 문제를 공유한 이유 : 스택이랑 큐를 너무 DFS / BFS에서만 사용해서 다른데서 사용하는 문제를 푸는 연습이 필요했음.

 

 

2. 사고하기

이거 스택 사용하려니까 사고하는거 자체가 어려워서 정답보면서 했다.

 

다른 사람들의 사고를 설명해보자면

1. 스택을 만든다.
2. 열린 괄호면 스택에 넣는데, tmp라는 변수를 밖에 만들어서 계산하는데 사용한다.

괄호별 값이 있으니 tmp에 곱해주면 됨

1. 닫힌 괄호를 만났을때

• 스택에서 제일위 top value를 pop했을때의 괄호 모양과 짝을 이루는가?

직전 문자와 짝(열린괄호)을 이룬다면 최종 결과변수 res에 tmp를 더해준다. >> 이부분 추가설명

 

짝이 안맞거나 스택이 비어있으면 아예 올바른 괄호열이 아니므로 res = 0 처리, break

무조건 마지막에 tmp /= (괄호별 값) 으로 이전 상태로 돌린다. 🔴🔴

[()]의 경우 ]를 만났을 떄 직전 문자가 )이므로 더하지 않고 넘어감 tmp만 수정

 

추가설명

짝을 이뤘을떄 tmp값이 뭐길래 최종 결과 변수에 더해주는것일까?

예제로 설명해보겠다.

(()[[]])([])

‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

라고 적혀있는데...

 

() == 2

[] == 3이고

[[]] = 3*3

() + [[]] = 2 + 3*3

(() + [[]]) = 2 * (2+33) = 2 * 2 + 2*3*3 = 4 + 18과 같다.

 

즉 tmp를 괄호 시작일떄 곱해주고, 닫힌괄호를 만났을 때 tmp를 res에 넣고 괄호값을 다시 나눠주는것.... 설명 드럽게 못하는것 같다. ㅎㅎㅠ

 

( : tmp = 1 * 2 = 2 , stack = (

( : tmp = 2 * 2 = 4 , stack = ((

) : stack의 top이 “(” 이고 짝이 맞다! res에 4 더해줌 >> 그다음

괄호식 위해 tmp =4/2 = 2 로 변경

여기까지 하면 위의 2 * 2 를 마무리한것이다.

이제 tmp가 2인 상태로 [ 를 만나면 3이 곱해지고, [를 만나면 3이 곱해지고 스택에 [ 넣고..  >> 2*3*3

] 를 만나 top인 [ 와 짝이 맞으므로 res에 18이 더해진다.

(233) 마지막으로 ]를 만났지만 직전이 짝꿍 [이 아니므로 그냥 tmp//3 만 해주고 넘어간다.

.

.

이런 과정의 반복이다... 

나중에 씨쁠쁠로 다시 풀어봐야지

 

 

정답코드

#2504_괄호의 값_구현 자료구조 스택 재귀_silver1
bracket = input()
length = len(bracket)
stack = []
tmp = 1
res = 0

for i in range(length):
    b = bracket[i]   
    if b == '(':
        tmp *= 2
        stack.append(b)
    elif b == '[':
        tmp *= 3
        stack.append(b)

    elif b == ')':
        if not stack or stack[-1] == '[':
            res = 0
            break
        if bracket[i-1] == '(':
            res += tmp
        tmp //= 2
        stack.pop()  
    else:
        if not stack or stack[-1] == '(':
            res = 0
            break
    # [()]의 경우 ] 직전 문자가 )이므로 더하지 않고 넘어감
    # 단, 이 경우는 오류는 아님 >> 지금까지 계산한거 한번만 해주면 되기 때문에...
        if bracket[i-1] == '[':
            res += tmp
        tmp //= 3
        stack.pop() 

if stack:
    res = 0
print(res)