[백준/Python] 2504 괄호의 값

 

괄호 문제.. stack으로 top과 현재 괄호를 비교해 짝을 이루는 괄호면 pop하고, 짝을 이루지 않으면 append하여 올바른 괄호열인지 구분하는 아주 기본적인 풀이가 있다.

이 풀이법을 응용하여 문제를 풀었는데,

중간중간에 곱하고 더하는 것을 어떤식으로 해야할지 고민을 하며 문제를 풀었다.

 

s = list(input())
stack = []
answer = 1  # 올바른 괄호열의 각 값을 계산
result = 0  # answer로 얻은 값들을 더해 정답을 담는 변수

# 1,2번은 괄호가 열릴 때 각각 2 또는 3을 곱해줌
# 3,4번은 괄호가 닫힐 때, answer에 있는 값을 result에 더한 뒤, 2 또는 3을 나눠주어 값을 원래대로 되돌림
# 만약 올바른 괄호열이 아닐 경우, 0으로!!
for i in range(len(s)):
    # 1
    if s[i] == '(':
        stack.append(s[i])
        answer *= 2

    # 2
    elif s[i] == '[':
        stack.append(s[i])
        answer *= 3

    # 3
    elif s[i] == ')':
        if s[i-1] == '(':
            result += answer
        if not stack or stack[-1] == '[':
            result = 0
            break
        stack.pop()
        answer //= 2

    # 4
    elif s[i] == ']':
        if s[i-1] == '[':
            result += answer
        if not stack or stack[-1] == '(':
            result = 0
            break
        stack.pop()
        answer //= 3

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

풀이과정

1. 각 괄호들의 값을 계산하는 것(answer)과 올바른 괄호열이 되었을 때 더해 구하는 값(result)를 따로 설정해두고 풀었고,

2. 괄호가 열릴 때마다 값을 곱해주도록 했다.( '('는 2, '['는 3 )

3. 괄호가 닫힐 땐, 각 괄호들의 값을 계산하는 answer을 2 또는 3으로 나눠주었는데, ( '('는 2, '['는 3 )

4. 그 이유는, 괄호가 닫혔으므로, 해당 계산을 끝이 났다고 생각하고, answer의 값을 그 전으로 되돌려야하기 떄문이다.

(아래에서 구체적인 예를 들어 설명하도록 하겠음!!!)

 

자세한 설명

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

예제1로 설명을 해보자면

우리가 구해야하는 식은 ' 2 x ( 2 + 3 x 3 ) + 2 x 3 ' 입니다.

위 식은 2 x 2 + 2 x 3 x 3 + 2 x 3으로 풀어서 쓸 수 있는데, 풀이과정 3을 하는 이유가 여기에 있습니다.

 

파란색 괄호( ( ) )와 노란색 괄호( [ [ ] ] ) 는 모두 빨간색 괄호( ( ) )로 둘러쌓여있어, 2가 각각 곱해져야 합니다.

( ( 두 괄호가 열리면서 2 x 2가 되는데,

파란색 괄호가 닫힌 후에는 파란색 괄호 때문에 곱해주었던 2를 나눠주어 빨간색 괄호때문에 곱해주었던 2만 남을 수 있도록 해야합니다.

그러면 노란색 괄호 ( [ [ ) 가 열리면서 곱해진 3 x 3 값이 2 와 곱해져서 우리가 원하는 값을 얻을 수 있게 되는 것입니다.

 

i = 0:

    answer = answer x 2 = 2

i = 1:

    answer = answer x 2 = 4

i = 2:

    result = result + answer = 4

    ansewr = answer // 2 = 2

i = 3:

    answer = answer x 3 = 6

i = 4:

    answer = answer x 3 = 18

i = 5:

    result = result + answer = 4 + 18 = 22

    answer = answer // 3 = 6

i = 6:

    answer = answer // 3 = 2

i = 7:

    answer = answer // 2 = 1

i = 8:

    answer = answer x 2 = 2

i = 9:

    ansewr = answer x 3 = 6

i = 10:

    result = result + answer = 22 + 6 = 28

    answer = answer // 3 = 2

i = 11:

    answer = answer // 2 = 1

 

∴ 답은 result = 28