[프로그래머스] 수식 최대화 복기

문제

https://programmers.co.kr/learn/courses/30/lessons/67257

코드

from itertools import permutations


def calculate(a, b, x):
    if x == "+":
        return int(a) + int(b)
    elif x == "-":
        return int(a) - int(b)
    else:
        return int(a) * int(b)


def solution(expression):
    answer = 0
    items = ["+", "-", "*"]

    lists = list(permutations(items))

    exp1 = []
    n = ''
    for s in expression:
        if s in items:
            exp1.append(n)
            n = ''
            exp1.append(s)
        else:
            n += s

    exp1.append(int(n))

    for imp in lists:  # imp =('+', '-', '*')
        exp2 = exp1[:]
        for im in imp:  # imp =('+', '-', '*') im = '+'
            e = 1  # 숫자
            stacks = []
            stacks.append(exp2[0])

            while True:
                if len(exp2) == 1:
                    answer = max(answer, abs(exp2[0]))

                    break

                if exp2[e] == im:
                    n = calculate(stacks.pop(), exp2[e + 1], exp2[e])
                    stacks.append(n)
                else:
                    stacks.append(exp2[e])  # 문자
                    stacks.append(exp2[e + 1])  # 숫자

                if e + 1 == len(exp2) - 1:
                    if len(stacks) == 1:
                        answer = max(answer, abs(stacks[0]))
                        break
                    break
                else:
                    e += 2

            exp2 = stacks

    return answer

설명

stack을 활용해서 풀이를 했는데요.. while문 탈출 조건을 명확하게 하지 못해서 시간이 많이 걸렸습니다.

e라는 인덱스를 활용해서 stack에 연산자 혹은 숫자를 넣어줍니다.
만약 연산자가 우선순위에 해당한다면, e 인덱스 다음 숫자와 stack의 마직막 숫자를 계산한 값을 stack에 넣어줍니다.

탈출조건은 exp1은 stack의 갱신한 값인데, 이때 exp1의 길이가 1일 때까지 for문을 돌려야합니다.
while문은 인덱스 기준으로 탈출하고, 두번째 for문은 최종 길이가 1일때 탈출해야 합니다.
이때 break가 아닌, continue로 설정하면 인덱스 오류가 날 수 있습니다.