[백준/python] 2504번: 괄호의 값

문제

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

2504번: 괄호의 값

---

문제 요약

'(', ')', '[', ']' 4개의 기호를 이용한 괄호열을 받는다.

 

올바른 괄호인지 확인하고 올바르지 못한 괄호열이면 0을 출력하고

 

1. 한 쌍의 괄호로만 이루어진 '()'와 '[]'는 올바른 괄호열이다.

2. 만일 x가 올바른 괄호열이면 '(x)'이나 '[x]'도 올바른 괄호열이 된다.

3. x와 y 모두 올바른 괄호열이라면 이들을 결합한 'xy'도 올바른 괄호열이 된다.

 

아니라면 조건에 따른 괄호열의 값을 출력한다.

 

1. '()'인 괄호열의 값은 2이다.

2. '[]'인 괄호열의 값은 3이다.

3. '(x)'의 괄호값은 2 × 값(x)으로 계산된다.

3. '[x]'의 괄호값은 3 × 값(x)으로 계산된다.

---

코드

import sys
input = __import__('sys').stdin.readline

def main():
    string = input().rstrip()
    st = []
    res = 0
    tmp = 1

    for i, ch in enumerate(string):
        if ch == '(':
            tmp *= 2
            st.append(ch)

        elif ch == '[':
             tmp *= 3
             st.append(ch)

        elif ch == ')':
            if not st or st[-1] == '[':
                res = 0
                break
            if string[i-1] == '(':
                res += tmp
            st.pop()
            tmp //= 2

        elif ch == ']':
            if not st or st[-1] == '(':
                res = 0
                break
            if string[i-1] == '[':
                res += tmp
            st.pop()
            tmp //= 3
            
    if st:
        print(0)
    else:
        print(res)

if __name__ == "__main__":
    main()

---

코드 설명

1. 반복문을 이용하여 입력 받은 string의 앞 쪽 인덱스부터 하나씩 접근한다.

 

2. 접근한 문자 ch가 열린 괄호 '(', '[' 라면 tmp에 2, 3을 각각 곱해주고 스택 st에 ch를 넣어준다.

 

3. 닫힌 괄호 ')', ']' 라면 먼저 올바른 문자열인지 확인한다.

=> 스택 맨 위 문자가 ch와 다른 문자이거나 스택이 비었다면 올바르지 못한 문자열이다.

(스택이 비었다면 이전에 열린 괄호가 들어오지 않은 것이다. 따라서 닫힌 괄호가 먼저 들어온 것이므로 올바르지 못한 문자열이다.)

=> 올바르지 않은 문자열이라면 출력할 res를 0으로 설정하고 반복문을 종료한다.

 

4. 올바른 문자열이라면, string에서 ch 앞에 오는 문자를 확인하여 '()' 또는 '[]' 인지 확인한다.

=> 맞다면 하나의 괄호. 즉 수식으로 표현했을 때 가장 깊이 있는 숫자이므로 res에 지금까지 곱해진 수 tmp를 더한다.

 

5. 닫힌 괄호일 때 3, 4번 과정이 끝났다면 마지막으로 스택에서 pop을 해준다.

또, tmp를 각 수에 해당하는 수(2, 3)로 나누어준다. (앞에서 계산한 값을 다시 계산하지 않게 하기 위해)

 

6. 반복문이 종료되었다면 스택을 확인한다. 스택에 요소가 남아있다면 0, 아니면 res를 출력한다.

+ 열린 괄호만 들어오고 닫힌 괄호가 들어오지 않았다면 스택에 요소가 남게 된다. => 올바르지 않은 괄호열

---

예를 들어 '(()[[]])([])'을 입력 받았다면 이를 수식으로 나타내면

2 × (2 + 3 × (3)) + 2 × (3) 이렇게 표현할 수 있다.

 

즉 '()', '[]'은 2, 3 숫자 자체를 나타내고, 그 외 자신의 짝과 떨어져 있는 '(', '['는 2 ×(?), 3 × (?)을 의미하는 것이다.

 

여기서 분배 법칙을 이용하면 알고리즘을 더 잘 이해할 수 있다.

위에서 나타낸 수식을 분배 법칙으로 푼다면

(2 × 2) + (2 × 3 × 3) + (2 × 3) = 4 + 18 + 6 이다

 

따라서 숫자 자체를 나타내는 괄호 '()', '[]' 를 찾았을 때마다 tmp (곱해져 있던 수)를 더해주는 것이다.

---

직접 예제 입력 1을 넣고 천천히 반복문을 따라가 보면 잘 이해할 수 있다.