백준 2504번: 괄호의 값 (G5) - Python 풀이

문제 설명

https://www.acmicpc.net/problem/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

문제 요약) 유효한 괄호 안에서 ()는 곱하기 2, []는 곱하기 3, ()[]는 2+3일 때, 입력 괄호에 대한 계산 결과를 출력해야 합니다.

 

풀이 과정

뭔가 상당히 익숙한 그것. 이라고 생각하고 스택을 사용해서 자신 있게 풀었습니다.
근데 그건 괄호의 수를 구하는 문제였습니다. 이건 곱하기… 만 있으면 또 나은데, ()[] 이런 경우에는 또 덧셈을 해야 합니다.

자신감 실종. 어떻게 하나요.
뭔가 )[ 또는 ]( 이렇게 엇갈리기 시작하는 구간에서 덧셈으로 바꿔야 하는 것 같은데 잘 모르겠습니다.
정답을 보겠습니다.

 

정답 코드

str = list(input())

stack = []
answer = 0
# (X) 또는 [X]일 때 X의 계산 결과를 담기 위한 변수
inner = 1

# 괄호 개수만큼 반복
for i in range(len(str)):
    # 괄호 열리는 경우
    if str[i] == "[":
        # 스택에 push
        stack.append(str[i])
        # 곱하기 3
        inner *= 3
    elif str[i] == "(":
        stack.append(str[i])
        inner *= 2
    # 괄호 닫히는 경우
    elif str[i] == "]":
        # 스택이 비어서 닫힌 괄호의 쌍이 될 값이 존재하지 않거나
        # 닫힌 괄호의 쌍이 될 값이 열린 괄호일 경우
        if not stack or stack[-1] == "(":
            # 유효하지 않은 괄호이기 때문에 0을 넣고 반복문 종료
            answer = 0
            break
        # 바로 이전 괄호의 값이 열린 괄호였다면 => inner 곱셈의 depth가 끝이라는 뜻 []
        elif str[i-1] == "[":
            # 현재까지 곱해진 값을 ans에 더한다
            answer += inner
        # 위의 if문에서 걸러지지 않았다면 현재 stack[-1]은 "["
        # 유효한 쌍을 찾았으니 pop을 통해 제거
        stack.pop()
        # 대괄호 쌍 찾아서 지웠으니까 이후 계산에 영향 안 가도록 3으로 나눠준다
        inner //= 3
    elif str[i] == ")":
        if not stack or stack[-1] == "[":
            answer = 0
            break
        # 바로 이전 괄호의 값이 열린 괄호였다면 => inner 곱셈의 depth가 끝이라는 뜻 ()
        elif str[i-1] == "(":
            # 현재까지 쌓인 곱셈 값을 ans에 더한다
            answer += inner
        stack.pop()
        inner //= 2
        
# for문 다 끝났는데 스택에 값이 남아 있다면
if stack:
    # 유효하지 않은 괄호니까 0 출력
    print(0)
else:
    # 아니면 ans 출력
    print(answer)

대충 나눗셈 로직을 생각하지 못 했던 것 같습니다.
이해가 안 되는 것 같다가도 은근 한 줄씩 뜯어보면 이해가 잘 됩니다.

1. 닫힌 괄호를 만날 때마다 나눗셈을 해서, 이후 계산에는 영향이 안 가도록 해야 합니다.
2. stack[-1]과 str[i-1] 둘 다 확인해야 합니다.

정확히 2번에서 스택이 있는데 이전 괄호를 왜 확인해야 되나 싶었는데 닫힌 괄호 확인할 때, 이전 괄호가 같은 종류의 열린 괄호일 수도 있고 다른 종류의 닫힌 괄호일 수도 있기 때문입니다. 이 경우를 다르게 처리해 줘야 합니다.

예를 들어 str가 [()] 이렇게 주어진다면 닫힌 괄호 ] 를 확인할 때 이전 괄호가 ) 가 됩니다. 이런 경우에는 answer += inner 코드를 거치지 않고 스택 pop과 나누기 3만 합니다.

반면에 닫힌 괄호 ) 를 확인할 때는 이전 괄호가 ( 이기 때문에 즉, 같은 종류의 열린 괄호라서 곱셈의 최대 depth에 도달한 것입니다. 이때 answer += inner 해서 이전까지 계산해온 곱셈 값을 answer에 한 번에 더하는 것입니다. 천재. 현재 괄호가 ) 일 때 inner는 곱하기 3와 곱하기 2를 거쳐온 6을 담고 있습니다. 이전 괄호가 ( 이니까 answer에 6을 더하고, 스택을 pop하고, inner는 나누기 2를 해서 3이 됩니다.

그 이후에 위에서 언급한 나누기 3을 해서 결국 inner는 1, answer는 6으로 잘 끝나게 됩니다.

 

왜 이렇게 모두가 자는 새벽에만 집중력이 500% 발휘되는 건지 모르겠네요.
해 떠 있을 때 이런 집중력이라면 더 바랄 게 없겠습니다.

이상입니다.