[BOJ][Python3]2504.괄호의 값

문제 유형: 구현

 

요번에는 어떻게든 풀었지만, 좋지 않은 코드의 예시다.

stack에 괄호 넣고 빼면서, 대체 어떻게 덧셈 + 곱셈을 구현하지? 라는 고민을 정말 많이 했다.

재귀로도 해보고, visited 배열을 만들기도 해보고 시도를 여러가지 하다 일반화가 잘 되지 않았다.

 

나름 해결한 방법으로는 score에 값을 하나씩 넣고 그 값에 대한 괄호 depth를 계산한 뒤, 같은 depth인 괄호는 더하고, 1 작은 depth를 만나면 곱하는 식으로 구현했다. 

 

풀이 설명

( () [ [] [] ] ) 

이면 하나씩 짝 맞춰질때마다 스택에서 빼고 score에 append하면

score = [ 2, 3, 3, 3, 2]

depth = [1, 2, 2, 1 , 0] 이다.

왼->오로 탐색하면서 최대 depth 를 가진 애들끼리 더하고, 더하다가 1 작은걸 만나면 곱해준다. 그러면 3 + 3 더하고 3 만나서 3 * (3+3) 으로 score[3]에 저장한다. 그리고 최대 depth 가진 애들은 빼고 다시 배열을 재구성한다

그러면

score = [ 2, 18, 2]

depth = [1, 1, 0] 

이 상태고 다시 반복...그러면 답이 나온다.

 

하지만 설명했다시피 좋지 않은 풀이다. 풀리긴 하다만 생각하기도 어렵고, 복잡함. 그리고 시간이 많이 걸림.

 

괜찮은 풀이 설명

다른 사람의 괜찮은 풀이를 서치해보니 곱셈의 분배법칙 감성이었다! temp와 res를 사용해서 곱하고, 더하고, 나누는 풀이었다.

즉 ( () [ [] [] ] ) 

이건 2 * ( 2 + 3 * (3 + 3 ) )

과 같은 식이지만, 2*2 + 2*3 *(3 + 3) 과도 같은 의미고 더 나아가 2*2 + 2*3*3 + 2*3*3과도 의미가 같다.

괄호를 시작할때 temp라는 변수에 곱하고, 괄호가 닫히면 temp를 답에 더해주고 괄호에 해당하는 수를 나눠준다.

개인적으로 이런 아이디어는 밤을 새서라도 떠올리기 어려웠을 것 같았다. 잘 기억해두고 나중에 써먹어야겠다.

 

 

나의 풀이

def sol(arr):
    stack = [arr[0]]

    score = []
    result = []
    depth = []
    flag = 0

    for i in range(1, len(arr)):
        top = ''
        if len(stack) != 0: top = stack[-1]

        if (top == '[' and arr[i] == ']') or (top == '(' and arr[i] == ')'):
            depth.append(flag)
            flag = flag - 1

            stack.pop()
            result.append(arr[i])
            if top == '[': n = 3
            if top == '(': n = 2

            score.append(n)

        else:
            flag = flag + 1
            stack.append(arr[i])

    if len(stack) != 0:
       return 0

    max_value = max(depth)

    while max_value > 0 :
        new_d = []
        new_s = []
        for i in range(len(depth) -1):

            if depth[i] == max_value and depth[i] == depth[i + 1]:
                score[i+1] += score[i]
            elif depth[i] == max_value and (depth[i+1] + 1 == (depth[i])):
                score[i+1] *= score[i]
            elif depth[i] != max_value:
                new_s.append(score[i])
                new_d.append(depth[i])
        new_d.append(depth[-1])
        new_s.append(score[-1])

        depth = new_d
        score = new_s
        max_value = max(depth)

    return sum(score)

bracket_arr = input()

print(sol(bracket_arr))