프로그래머스 [Lv. 2] 수식 최대화 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

from collections import deque

def solution(expression):
    answer = 0
    orders = [
        ["+", "-", "*"], 
        ["+", "*", "-"],   
        ["*", "+", "-"], 
        ["*", "-", "+"], 
        ["-", "+", "*"],
        ["-", "*", "+"]
    ]
    
    expression += "/"
    arr = []
    
    number = ""
    for exp in expression:
        if "0" <= exp <= "9":
            number += exp
        else:
            arr.append(int(number))
            if exp != "/":
                arr.append(exp)
            number = ""
    
    def cal(left, right, o):
        if o == "+":
            return left + right
        elif o == "*":
            return left * right
        else:
            return left - right
    
    for order in orders:
        stack = []
        tmp = deque(arr)
        for o in order:
            while tmp:
                a = tmp.popleft()
                if type(a) == number:
                    stack.append(a)
                else:
                    if a == o:
                        left = stack.pop()
                        right = tmp.popleft()
                        stack.append(cal(left, right, o))
                    else:
                        stack.append(a)
            tmp = deque(stack)
            stack = []
        value = abs(tmp.popleft())
        if answer < value:
            answer = value
            
    return answer

풀이 방법

1. 서로 다른 우선순위를 가진 연산자를 orders에 저장한다.
2. 문자열을 숫자와 연산자로 분리한다.
3. orders의 order에 먼저나온 o("+", "-", "*")가 높은 우선순위를 가지므로 먼저 계산한다.
4. tmp를 앞에서 부터 빼면서 숫자면 우선 stack에 넣고 연산자면 확인한다.
5. o와 일치하면 stack에서 하나를 빼서 o를 계산한 뒤 다시 stack에 넣는다.
6. tmp가 다 비었으면 tmp를 다시 stack의 값으로 치환하고 stack은 비운다.
7. 이 과정을 반복하고 나온 값에 절대값을 씌운 뒤 최대값과 비교한다.
8. 마지막에 answer를 반환하면 끝!

느낀점

• 다른 방법도 있겠지만 stack과 queue을 활용해 보고 싶었다.