[BOJ] 2504. 괄호의 값

📌 문제 제목

문제 링크: BOJ 2504

---

🗒️ 문제 설명

소괄호와 대괄호만을 이용해 만들어진 괄호열이 있다.

입력이 올바르지 못한 괄호열이면 0을 출력하고, 올바른 출력이면 아래의 내용을 참고하여 출력하라.

• '()'인 괄호열의 값은 2이다.
• '[]'인 괄호열의 값은 3이다.
• '(X)'인 괄호열의 값은 2 x 값(X)으로 계산된다.
• '[X]'인 괄호열의 값은 3 x 값(X)으로 계산된다.
• 올바른 괄호열 x와 y가 결합된 xy의 괄호값은 값(xy) = 값(x) + 값(y)으로 계산된다.

e.g. ( ( ) [ [ ] ] ) ( [ ] )의 괄호값은 28이다.

2 * (2 + (3 * 3)) + 2 * 3 = 22 + 6 = 28

 

시간 제한: 1초

메모리 제한: 128MB

1 <= ps(괄호 문자열) <= 30

---

💡 문제 해결 아이디어

• 여는 괄호는 스택에 추가
• 닫는 괄호
  
  • 스택의 마지막 원소가 각 괄호의 여는 괄호가 아니면 0 출력
  • 스택의 마지막 원소가 숫자라면 tmp라는 변수를 만들고 스택의 마지막 원소가 숫자가 아닐 때 까지 pop하며 tmp에 값을 더함.
    • 소괄호라면 tmp x 2, 대괄호라면 tmp x 3을 스택에 추가
• 순회가 끝나면 스택에 남아있는 숫자들을 answer에 더함.

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

ps = input().strip()


def solution(ps: str) -> int:
    answer = 0
    stk = []

    for b in ps:
        if b == '(' or b == '[':
            stk.append(b)
        elif b == ')':
            if not stk:
                return 0

            if stk[-1] == '(':
                stk.pop()
                stk.append(2)
            elif isinstance(stk[-1], int):
                tmp = 0
                while stk and isinstance(stk[-1], int):
                    tmp += stk.pop()
                if not stk or stk[-1] != '(':
                    return 0
                stk.pop()
                stk.append(2 * tmp)
            else:
                return 0
        elif b == ']':
            if not stk:
                return 0

            if stk[-1] == '[':
                stk.pop()
                stk.append(3)
            elif isinstance(stk[-1], int):
                tmp = 0
                while stk and isinstance(stk[-1], int):
                    tmp += stk.pop()
                if not stk or stk[-1] != '[':
                    return 0
                stk.pop()
                stk.append(3 * tmp)
            else:
                return 0

    for val in stk:
        if isinstance(val, int):
            answer += val
        else:
            return 0

    return answer


print(solution(ps))