백준 - 2504. 괄호의 값

[백준] 2504. 괄호의 값

Link 실버 1티어 문제

문제

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 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

예제 입력 1

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

예제 출력 1

28

풀이

아이디어를 떠올리는 것이 중요했던 문제였다고 생각한다.

괄호의 짝이 맞는지 구하는 것은 앞선 여러가지 괄호문제에서 Stack을 활용하면 쉽게 해결할 수 있었지만, 출력을 만들어내기 위한 계산의 순서가 뒤죽박죽으로 느껴져 생각해내기 어려웠다.

예제 입력 1 부터 어떻게 28이 나오는지 살펴보자. ({}로 괄호를 대체해서 표현하겠다.)

괄호의 종류를 파악하고 숫자로 치환하고, 그 합계를 얻어내는 순서가 너무나도 뒤죽박죽이다.

이는 Stack을 사용하여 Valid한 괄호인지 파악하고 짝인지 확인하는 순서와 그때그때 최종적으로 수의 합계를 얻는 순서가 다르기때문이다.

이를 해결할 두가지 방법이 떠오르는데..

1. Stack에 숫자를 넣고 빼면서 처리하는 방법
2. 분배법칙을 사용하여 수퍼포지션 형태로 바꿔 계산의 순서를 바꾸는 방법

처음에 1로 해보려고 했지만 실패해서 2로 작성하겠다.

만약 분배법칙을 사용하지 않고 숫자가 나오는 순서대로 계산을 한다면

1. () -> 2
2. [] -> 3
3. [3] -> 9
4. 2+ 9 = 11
5. (11) = 22

이러한 순서가 된다. 괄호 안에 값을 먼저 구하고 그 다음 곱해주는 방식이다.

하지만 분배법칙으로 하게된다면

1. ( -> 2
2. (() -> 4
3. ([] -> 6
4. ([6] -> 12
5. …

이런식으로 같은 괄호안에 있다면 값을 먼저 곱해준 다음 순서대로 더해주기만 하면 된다.

이를 참고하여 코드를 작성해보자.

1. 괄호를 저장하고 짝이 맞는지 확인하기 위해 stack 을 생성
2. 최종 정답과 중간중간의 값을 저장할 answer와 temp 생성
3. 괄호 문자열을 s에 저장
4. s[i]가 ‘(‘ 또는 ‘[’ (여는 괄호)라고 한다면 stack에 append하고 2나 3을 temp에 곱해준다.
5. 닫는 괄호라면 먼저 stack안에 성분이 있는지, 또는 닫는괄호 s[i]와 stack[-1]이 짝이 맞는지 확인하고, stack에 성분이 없거나 짝이 맞지 않으면 answer에 0을 대입하고 break한다.
6. 닫는 괄호면서 짝이 맞고 stack에 성분이 있고, 바로 이전 괄호가 같은 타입의 여는 괄호라면 answer에 temp를 더해준다.
   • 이는 같은 값을 중첩해서 더해버리는 것을 막기위한 것으로 [[]]가 있을 때 마지막 ]가 올때는 answer에 값을 더해주지 않아야 하기 때문
7. stack[-1]을 pop하고 temp에 곱해졌던 2나 3값을 나눠준다. (분배법칙이 끝났기 때문)
8. stack안에 괄호가 남아있으면 짝이 맞지않는 괄호 문자열이기 떄문에 0을, stack이 비어있으면 answer를 print한다.

s = input()
stack = []
answer, temp = 0, 1

for i in range(len(s)):
    if s[i] == '(':
        stack.append(s[i])
        temp *= 2

    elif s[i] == '[':
        stack.append(s[i])
        temp *= 3

    elif s[i] == ')' :
        if not stack or stack[-1] != '(':
            answer = 0
            break
        if s[i-1] == '(':
            answer += temp

        stack.pop()
        temp = temp // 2
        
    else:
        if not stack or stack[-1] != '[':
            answer = 0
            break
        if s[i-1] == '[':
            answer += temp

        stack.pop()
        temp = temp // 3
     
if stack:
    print(0)
else:
    print(answer)