[TIL][Krafton Jungle] 1주차 (sub) : 스택 문제

2주차가 시작 되기 전 아침.

 

밤에 자면서 아무리 생각해도 방법이 떠오르지 않던 문제를 풀었다.

 

---

 

Baekjun - #2504 괄호의 값 (스택 : 상)

처음엔 재귀함수를 써야하나 했다.

 

괄호의 특성 상 안의 연산들을 전부 기억 한 후 곱연산을 수행해야 했기 때문에 재귀방식이 먼저 떠올랐지만 어떻게 재귀로 풀어내야 할지 도무지 답이 안나왔다.

 

이 문제는 괄호에 숫자는 없지만 괄호의 종류 별로 값을 부여해 제일 서로 옆끼리 붙어있는 애들은 더하고,

속해있는 애들은 겉에 애가 곱해주는 문제를 수행해야 했다.

 

각 케이스 별로 따로 처리하려고 했으나 그 방법으론 처리되지 않는 케이스가 너무 많아서 구글링을 하니까

'분배법칙'을 사용하라는 얘기를 듣고 방법을 자세히 들여다 봤다.

 

출처 : https://eunsolsblog.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-2504%EB%B2%88-%EA%B4%84%ED%98%B8%EC%9D%98-%EA%B0%92

 

2 x ( 2+ 3x(3)) = (2 x 2) + (2 x 3 x(3)) 과 같다는 분배법칙을 이용하면

코드로 잘 풀어낼 수 있었다.

 

from collections import deque
import sys


words = list(map(str,sys.stdin.readline().strip()))
count = 0

def check_is_right():
    global count
    state = None  #open = "O" #close = "C"
    if len(words) %2 == 1:
        return 0
    stack = [0]
    temp = 1
    while words:
        word = words.pop(0)
        if word == '(' or word == '[':
            if word == '(':
                temp *= 2
            else :
                temp *= 3
            stack.append(word)
            state = "O"
        elif word == ')' or word == ']':
            check = stack.pop()
            if check == '(' and word == ')':
                if state == "O":
                    count += temp
                temp //= 2
                state = "C"
            elif check == '[' and word == ']':
                if state == "O":
                    count += temp
                temp //=3
                state = "C"
            else :
                return 0
    return count

print(check_is_right())

 

---