[백준] #2504 괄호의 값 (python)

2504번: 괄호의 값 (acmicpc.net)

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

출력

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

 

예제 입력1

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

예제 출력1

28

예제 입력2

[][]((])

예제 출력2

0

 

---

 

# Code

import sys
input = sys.stdin.readline

s = input().rstrip() #'\n' 제거하기 위함.
stack = []
tmp = 1
result = 0

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] == "[":
            result = 0
            break
        if s[i-1] == "(":
            result += tmp
        stack.pop()
        tmp //= 2
    else:
        if not stack or stack[-1] == "(":
            result = 0
            break
        if s[i-1] == "[":
            result += tmp
        stack.pop()
        tmp //= 3  

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

 

# Comment

하.. 일단 야심차게 처음에 작성한 코드는... 걍.. 쓰레기였다. 일단 []([]) 이런 케이스는 고려했는데 ([]([])) 이런 케이스는 전혀 고려되지 않은.. 바보같은 코드였다.. ㅠㅠ 도대체 저 안에서의 덧셈을 어떻게 구현해야하는지 겁나 고민하다가.. 나같은 빡대갈은 고민해도 못 풀 것 같은 삘이 강하게 왔다. 그래서 결국 구글링해서.... 하나하나 그려가면서 따라했다...

 '(' 괄호가 나오면 2를 곱해주고 '[' 괄호가 나오면 3을 곱해준다.

그리고 괄호를 닫은 경우에는 계산한 값을 저장한 후에 누적 계산은 다시 나누기 2나 3을 해주어 원래대로 값을 돌린다.

닫는 괄호가 올 때, 내가 괄호를 하나하나 집어 넣는 stack 리스트가 아니라, 처음에 입력받은 괄호 배열인 s 리스트의 직전 괄호와 짝이 맞을 경우에만 곱한 값을 결과에 더한다.

' [ ( ) ] ' 의 경우 마지막 ' ] ' 의 바로 직전의 괄호가 ' [ ' 가 아닌 ' ) ' 이기 때문에 값을 더해가지 않는다.

우리가 계산해야 할 것은 3 x 2 = 6인데 앞에서 곱하기 3은 이미 계산을 했기 때문에 뒤에서 더 계산을 하면 안되기 때문이다. 

 

' [ ( ) ] [ ] ' 의 경우를 보자.

코드에서 짚어 보면, 처음에 ' [ ' 가 들어왔으므로 tmp에 3이 곱해져 tmp = 3,  다음으로 ' ( ' 가 들어왔으므로 tmp = 6,

그다음 ' ) ' 는 바로 앞의 ' ( ' 와 짝을 이루므로 result = 6이 되고 tmp // 2 = 3, ' ] ' 는 앞이 ' [ ' 가 아닌 ' ) ' 이므로 result에 tmp를 더하지 않고, tmp // 3 = 1 이 된다.  

이제 다시 ' [ ] ' 를 계산해야 한다. tmp가 1로 초기화 됐으므로, ' [ ' 가 올 때 tmp에 3이 곱해져 tmp = 3,  그 다음 ' ] ' 가 올 때 앞의 괄호와 짝이 맞으므로 result = result + 3 = 6+3 = 9 가 된다.

 

' [ ] ( ( ] ) ' 의 경우를 보자.

처음 ' [ ] ' 는 위의 경우와 똑같이 계산해서 result = 3 이 되고, tmp는 3으로 나누어져서 1이 된다.

' ( ( ' 까지 들어왔을 때 tmp = 4, ' ] ' 는 앞의 괄호와 짝이 맞지 않으므로 result = 0 이 되고 break 문을 통해 반복문을 빠져나온다.

 

휴.. 계속 헷갈렸는데 쓰면서 조금 이해가 되는 것 같다. 자고 일어나서 한 번 더 풀어볼 예정이다. 또 다른 풀이가 보고 싶어서 백준에 다른 풀이를 봤는데.... 딕셔너리? 를 사용하신 분들이 많았다.. 풀이 시간도 겁나 짧고... 풀이를 봤는데 뭔 소린지 모르겠더라 ㅎㅎ 열심히 공부하자 ... ^^ 오늘은 골드 괄호 문제를 풀 예정인데 아주 걱정이다 ㅎㅎ

 

2/11 베이징 올림픽 쇼트트랙 제발 ㅠ ㅠ 중국 때문에 억울한 일 없었으면 좋겠다. 기대되면서도 너무 걱정된당...

쇼트트랙 화이탱