[백준/2504/파이썬] 괄호의 값

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

2504번: 괄호의 값

Problem

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 이다.

SOL

괄호의 쌍을 찾는 문제이다. 괄호의 쌍을 찾는 문제는 간단해 보이면서도, 막상 구현을 하게되면 헷갈리게 되는

마법 같은 문제니까, 하나씩 차근차근 접근해야한다.

 

우리는 괄호 전체를 입력 받고, 괄호가 1~30개밖에 안되기 때문에, 괄호를 하나씩 검사하면서 반복을 할거다.

 

우선, "0"이 출력되는 경우를 생각해보자.

• stk[top]과 다른 종류의 닫히는 괄호가 오는경우. 예를들어, ((]) 와 같이, stk의 top에는 "("가 있는데, "]"가 입력으로 들어오는 경우.
• 반복을 끝냈는데도, stk이 비지않은 경우.
• 먼저 닫힌 괄호가 입력되는 경우.(stk이 비었는데, "]"만 들어오는 경우)

그럼, 위의 조건대로 어떻게 계산을 해줄지 생각을 해보자.

우선, (x)의 값은, 2*x 즉, x의 값이 누적되어서 2를 곱하게 된다. 예를들어, ([]()) 같은경우는, 2*(3+2)이고, 10이된다.

곱셈은 분배법칙이 일단 성립하기 때문에, 2를 누적해서 곱해주는 개념으로 접근해도 된다. 

 

Trouble Shooting

• 누적해서 곱해주는 방법으로 접근했더니, ([])와같은 예시에서, 2*3+2가되는 불상사가 발생하였다.
• 왜나하면, stk에서는 "("가 남아있는 상태에서, ")"가 들어오는거니까, +2가 나중에 되는것처럼 보이게 되는거다.

import sys
input = sys.stdin.readline

# (),[]
lst=input().rstrip()
stk=[]
top=-1
ans=0
tmp=1

for i in range(len(lst)):
    if lst[i] =="(":
        stk.append(lst[i])
        tmp *=2
    elif lst[i]=="[":
        stk.append(lst[i])
        tmp *=3
    elif lst[i]==")":
        # 괄호의 쌍이 닫혔다면?
        if not stk or stk[top]=="[":
            ans=0
            break
        if stk[top] == "(":
            ans+=tmp
        stk.pop()
        tmp //=2
    elif lst[i]=="]":
        if not stk or stk[top]=="(":
            ans=0
            break
        #stk의 top이 기준이 되면, (())에서, tmp= 2*2 +2로, 한번 더 더해진다. 
        #그 전에 입력받은 값을 기준으로 하면 편하다.
        if stk[top]=="[":
            ans+=tmp
        stk.pop()
        tmp //=3
    #print(f"tmp:{tmp},ans:{ans},stk{stk}")

if stk:
    print(0)
else:
    print(ans)

• 즉, "("다음 ")"오는것과, 나중에 닫히는걸 구분시켜 줘야한다. 다른 말로하면, 괄호가 바로 닫히는 건지 , 괄호가 나중에 닫히게 된거인지 구분을 해야한다. 따라서, 괄호가 바로 닫히는 경우에만, ans에 더해주면 된다!
• " ( " 다음 ")" 오는 경우에만 ans에 더해주고, 나머지 경우에는 pass 해주면된다. 예를들어, ")",")"같은 경우

정답 코드

import sys
input = sys.stdin.readline

# (),[]
lst=input().rstrip()
stk=[]
top=-1
ans=0
tmp=1

for i in range(len(lst)):
    if lst[i] =="(":
        stk.append(lst[i])
        tmp *=2
    elif lst[i]=="[":
        stk.append(lst[i])
        tmp *=3
    elif lst[i]==")":
        # 괄호의 쌍이 닫혔다면?
        if not stk or stk[top]=="[":
            ans=0
            break
        if lst[i-1] == "(":
            ans+=tmp
        stk.pop()
        tmp //=2
    elif lst[i]=="]":
        if not stk or stk[top]=="(":
            ans=0
            break
        #stk의 top이 기준이 되면, (())에서, tmp= 2*2 +2로, 한번 더 더해진다. 
        #그 전에 입력받은 값을 기준으로 하면 편하다.
        if lst[i-1]=="[":
            ans+=tmp
        stk.pop()
        tmp //=3
    #print(f"tmp:{tmp},ans:{ans},stk{stk}")

if stk:
    print(0)
else:
    print(ans)