[BOJ] 2504. 괄호의 값(🥇, 스택/큐)

문제

풀이

스택 자료구조를 이용한 풀이

• 괄호
  열린 괄호((, [) 라면 무조건 스택에 넣고, 닫힌 괄호(), ])라면 스택에 짝이 맞는 열린 괄호가 있는지 확인하는 방식

• 숫자
  모든 괄호들의 짝이 맞다고 가정

• 열린 괄호 + 닫힌 괄호 : 바로 숫자를 추가

• 숫자 + 숫자 : 두 개의 숫자를 더해서 다시 추가

• 열린 괄호 + 숫자 + 닫힌 괄호 : 숫자와 열린/닫힌 괄호의 숫자를 곱해준다

# 44ms

bkt = input()
stack = ['']

def check():
    value = {']': 3, ')': 2}
    pair = {']': '[', ')': '('}
    for b in bkt:
        if b in ('(', '['):
            stack.append(b)
            continue

        if type(stack[-1]) != int and stack[-1] != pair[b]:
            return 0

        if type(stack[-1]) == int:
            if stack[-2] != pair[b]:
                return 0
            tmp = stack.pop() * value[b]
            stack.pop()
            stack.append(tmp)
        else:
            stack.pop()
            stack.append(value[b])
		
        # 숫자 + 숫자가 있는 경우 두 개의 숫자를 꺼내고 더해서 다시 추가해주는 방식
        if len(stack) > 3 and type(stack[-1]) == type(stack[-2]) == int:
            tmp = stack.pop() + stack.pop()
            stack.append(tmp)


    if len(stack) > 2 and type(stack[-1]) == type(stack[-2]) == int:
        tmp = stack.pop() + stack.pop()
        stack.append(tmp)

    if len(stack) > 2 or type(stack[-1]) != int:
        return 0
    else:
        return stack[-1]

print(check())

풀리긴 했지만 어메이징한 파이썬이라서 풀린 문제. 스택에 괄호(문자열)와 숫자가 같이 들어가기 때문에 다른 언어로는 시도할 수 없는 방식이었다.

괄호와 숫자를 담을 스택을 따로 두는 방법도 생각했지만 그렇게 되면 어느 시기에 들어온 숫자인지를 저장할 정보도 필요하기 때문에 오히려 더 복잡해지는 것 같아서 이 방법을 택했다.

괄호는 스택으로, 숫자는 변수로

이 블로그의 코드 참조

일단 열린 괄호가 들어오면 무조건 숫자를 곱하고, 닫힌 괄호가 들어오면 바로 직전의 괄호가 열린 괄호인 경우에만 누적된 값을 더해준다. 누적된 값을 원래대로 되돌려야 하기 때문에 무조건 곱했던 숫자로 나눠준다

bracket = list(input())

stack = []
answer = 0
tmp = 1

for i in range(len(bracket)):

    if bracket[i] == "(":
        stack.append(bracket[i])
        tmp *= 2

    elif bracket[i] == "[":
        stack.append(bracket[i])
        tmp *= 3

    elif bracket[i] == ")":
        if not stack or stack[-1] == "[":
            answer = 0
            break
        if bracket[i-1] == "(":
            answer += tmp
        stack.pop()
        tmp //= 2

    else:
        if not stack or stack[-1] == "(":
            answer = 0
            break
        if bracket[i-1] == "[":
            answer += tmp

        stack.pop()
        tmp //= 3

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

재귀를 이용한 풀이

열린 괄호가 들어오면 재귀를 통해 내부의 괄호들을 탐색해 값을 return 한다. return 된 값에 숫자를 곱해주는 방식. 괄호가 올바르지 않거나 한다면 sys.exit()를 통해 ans의 값에 상관없이 0이 출력되고 프로그램이 강제 종료된다.

입력받은 문자열을 거꾸로 뒤집어서 앞에 있는 값부터 pop()해서 꺼냈다. 이러면 인덱스의 값들이 바뀔 필요가 없어서 더 빠른가?

참고한 블로그

import sys
input = sys.stdin.readline

s = list(input().rstrip())[::-1]

def cal(start):
    r = 0
    while s:
        a = s.pop()
        if a == "(" or a == "[":
            r += cal(a)
        elif start == "(" and a == ")":
            return 2 * max(1,r)
        elif start == "[" and a == "]":
            return 3 * max(1,r)
    
    # 리스트가 비었는데 최종 return 하지 못했다는 것은 괄호에 문제가 있음을 의미
    print(0)
    sys.exit()

ans = 0    
while s:
    ans += cal(s.pop())
print(ans)

후기

스택... 괄호...