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

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

프로그래머스

풀이

처음에는 재귀를 써야하나 브루트포스인가 고민했는데, 자료구조 문제였던 것 같다. 나 같은 경우에는 우선순위 큐를 사용해서 풀었다. 먼저 수식을 숫자와 연산자로 나눠준다. 그 다음 모든 경우의 수(연산자 우선순위의 경우의 수)를 탐색하면서, 만약 연산자가 현재 우선순위 연산자면 계산해주고 새로운 큐에 넣어주고, 만약 아니면 그냥 큐에 넣어줬다. 이 작업이 끝나고 나면 큐에는 숫자 하나만 남으므로, answer랑 비교해서 더 크면 answer에 할당해주면 된다.

from collections import deque
from itertools import permutations
def solution(expression):
    answer = 0
    exp_q = deque()
    tempt_s = ''
    op = ['+', '-', '*']
    for i in range(len(expression)):
        if expression[i] in op:
            exp_q.append(tempt_s)
            tempt_s = ''
            exp_q.append(expression[i])
        else:
            tempt_s += expression[i]
    exp_q.append(tempt_s)
    posi = list(permutations(op, 3))
    n2 = ''
    for pos in posi:
        q = deque(exp_q[i] for i in range(len(exp_q)))
        for p in pos:
            tempt_q = deque()
            while q:
                s = q.popleft()
                if s in op:
                    if s == p:
                        n1 = q.popleft()
                        tempt_q.pop()
                        tempt_q.append(str(eval(n2+s+n1)))
                        n2= str(eval(n2+s+n1))
                    else:
                        tempt_q.append(s)
                else:
                    tempt_q.append(s)
                    n2 = s
            q = tempt_q.copy()
        if answer < abs(int(q[0])):
            answer = abs(int(q[0]))
    return answer