Site avatar

☀️ Log

개발과 학습에 대한 생각을 기록하는 공간입니다.

GitHub

2504. 괄호의 값

4 min read

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초128 MB73080215811630131.809%

문제

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

풀이

실패

from collections import deque  
def checkSameLv(close):  
    global i  
    close = close[0]  
    score = close[1]  
    sum = 1  
    stk.append(p[i])  
  
    while True:  
        if i >= I:              # 다 안 닫혔는데, input 끝남  
            print(0)  
            exit()  
  
        if p[i] == close:       # 제대로 닫힘  
            return score * sum  
  
        if p[i] in closes:       # 새로운게 열리면.  
            sum += checkSameLv(closes[p[i]])  
            continue  
        else:                   # 다른게 닫히면  
            print(0)  
            exit()
 
p = input()  
closes = {'(': (')', 2), '[': (']', 3)}  
i = 1  
I = len(p)  
stk = deque()  
stk.append(p[0])  
result = 0  
while i < I:  
    result += checkSameLv(closes[p[i]])  
  
if len(stk) == 0:  
    print(result)  
else:  
    print(0)
  • 괄호 깊이를 기준으로 재귀를 돌려 풀려고 했는데, 예제부터 재귀가 깊다고 실패 → 코드 자체를 잘걸 수도 있음

성공

from collections import deque  
  
p = input()  
stk = deque()  
closes = {'(': ')', '[': ']'}  
scores = {')': 2, ']': 3}  
  
for i in range(len(p)):  
  
    if p[i] in closes:  
        stk.append(p[i])  
        continue  
  
    # pop을 해야함  
    add = 0  
    while True:  
        if len(stk) == 0:  
            print(0)  
            exit()  
  
        if isinstance(stk[-1], int):  
            add += stk.pop()  
            continue  
  
        close = closes[stk[-1]]  
        score = scores[p[i]]  
        if p[i] == close:        # 제대로 닫힘  
            stk.pop()  
            stk.append(max(score, score * add))  
            break  
        else:  
            print(0)  
            exit()  
try:  
    print(sum(stk))  
except:  
    print(0)