백준 2504 괄호의 값 Python

문제설명

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을 출력해야 한다.

예제

---

이 문제의 key포인트

-> 문제를 풀기 위한 아이디어를 파악하는 것이 중요한 문제이다.

-> 스택의 특성을 잘 이해하는 것이 중요하다. 

---

자료구조 및 알고리즘: 구현, 스택

---

문제풀이

사담)

문제를 풀다보면 내 힘으로는 죽어도 안풀리는 문제들이 있다. 나에겐 이 '괄호의 값' 문제가 그런 문제였다.

시간을 투자해도 안풀려서 풀이를 보았는데, 사실 풀이를 봐도 아이디어를 이해하지 못했다.

다음은 끙끙대면서 결국 이해한 풀이 아이디어이다. 혹시 나와같이 풀이를 봐도 이해가 가지 않는 분들을 위해 과정을 자세하게 적어보았다. 도움이 되었으면 좋겠다 ㅜㅜ 

 

먼저 알고리즘은 다음과 같다.

tmp값이 중간중간 계산될 괄호의 값이 되고, 초기값은 1이다. result값은 최종적인 괄호의 값이며 초기값은 0이다. 

앞에서부터 문자열을 탐색하면서 

1. 열린괄호 ('(' 또는 '[')가 나오면

        (1) tmp에 2나 3을 곱해준다.

        (2) stack에 문자열을 저장한다. 

2. 닫힌괄호 (')' 또는 ']')가 나오면

        (1) 현재 문자열 바로 앞의 문자열이 닫힌 괄호와 짝을 이룬다면 한 괄호의 케이스가 끝난 것이기 때문에

              result에 tmp값을 더해준다.

        (2) stack이 비지 않았고, stack[-1]이 현재 값과 짝이 맞다면 괄호를 다 쓴 것이므로 tmp값을 2나 3으로 나눠주고,

              stack.pop()을 해준다. 

3. stack이 아직 비어있지 않다면 올바르지 않은 괄호이므로 0을 출력한다.

 

예제 1번을 보면 주어진 문자열이

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

이다. 우리는 이 중에서 

(()[[]])

이 부분만 본다.

예제 설명에 나온 것과 같이 이 부분의 값은 2×(2 + 3×3)으로 22가 된다. 

이 식을 분배법칙으로 풀어보면  2×2 + 2×3×3 이렇게 된다.

문자열을 앞에서부터 탐색하며

알고리즘을 따라가면 적어본 과정이 다음 그림이다. 

첫번째 풀이

코드(완성코드, 맞았습니다!!, 44ms)

string = list(input().strip())

def get_value():
  stack = []
  tmp = 1
  result = 0
  for i in range(len(string)):
    cur_letter = string[i]
    if cur_letter == '(':
      tmp *= 2
      stack.append(cur_letter)
    elif cur_letter == '[':
      tmp *= 3
      stack.append(cur_letter)
    elif cur_letter == ')':
      if not stack or stack[-1] != '(':
        result = 0
        break
      if string[i - 1] == '(':
        result += tmp
      tmp //= 2
      stack.pop()
    else:
      if not stack or stack[-1] != '[':
        result = 0
        break
      if string[i - 1] == '[':
        result += tmp
      tmp //= 3
      stack.pop()
  if stack:
    result = 0
  return result

print(get_value())