Week 01 ~ 04 : 알고리즘 문제 풀이

파이썬 백준 2504 괄호의 값

정글러 2021. 11. 13. 01:18
before = list(input())
origin = ['((', '([', '[(', '[[', '))', ')]', '])', ']]', '()', '(]', '[)', '[]', ')(', ')[', '](', '][']
translation = [[2, 1], [2, 1], [3, 1], [3, 1], [2, -1], [3, -1], [2, -1], [3, -1], 2, 0, 0, 3, '+', '+', '+', '+']
trl = []
for i in range(len(before) - 1) :
    for j in range(16) :
        if before[i] + before[i+1] == origin[j] :
            trl.append(translation[j])

# (()[[]])([]) -> '2*(' '2' '+' '3*[' '3' ']' ')' '+' '2*(' '3' ')'  
         
if len(trl) != len(before) - 1 :
    trl = [0]

def calc(l) :
    n = len(l)
    if 0 in l :
        l = [0]
    else :
        for i in range(n) :
            if type(l[i]) is int and i > 0 and i < n - 1 :
                if type(l[i-1]) is list and type(l[i+1]) is list :
                    if l[i-1][0] == l[i+1][0] and l[i-1][1] > l[i+1][1] :
                        l[i] = l[i] * l[i-1][0]
                        l[i-1] = 'done'
                        l[i+1] = 'done'
            elif l[i] == '+' and i > 0 and i < n - 1 :
                if type(l[i-1]) is int and type(l[i+1]) is int :
                    l[i] = l[i-1] + l[i+1]
                    l[i-1] = 'done'
                    l[i+1] = 'done'
        while 'done' in l :
            l.remove('done')

maxlen = 30
for i in range(maxlen//2) :
    calc(trl)
if len(trl) == 1 and type(trl[0]) is int :
    print(trl[0])
else :
    print(0)

스택을 쓰는 문제라길래 일단 괄호를 리스트의 형태로 바꿨는데,

잘 보니까 위의 주석처럼 그냥 괄호열을 왼쪽부터 쭉 해독해서 하나의 수식으로 만드는게 가능하다.

리스트 형태로 나온 수식을 잘 가공해서 int형의 답을 뽑으면 끝

 

스택은 안썼지만 문제 태그에 구현이 있으니 아무튼 구현하면 된게 아닐까?

혹시 수요일까지 이번주차를 다 풀면 남는 시간에 스택을 써봐야겠다.