[프로그래머스] 수식 최대화 / 2020 카카오 인턴십 / python

연산자들('*', '+', '-')의 순열을 하나씩 확인하여 모든 우선 순위 경우의 수를 확인해봐야 한다.

확인해보는 과정은 아래와 같다.

• 주어진 식이 "100-200*300-500+20"일 때, numbers = [100, 200, 300, 500, 20]와 operator = ['-', '*', '-', '+']로 구분한다.
• number_stack과 operator_stack을 준비한다.
• number_stack에 먼저 numbers의 첫번째 숫자를 꺼내서 넣는다.
• 이제 numbers와 operators에서 첫번째 요소를 하나씩 꺼내고 두 배열이 빌 때까지 아래 과정을 반복한다.
  • operator가 현재 우선 순위에 해당하는 연산자일 경우: 꺼낸 요소들로 number_stack의 맨 마지막 요소와 계산하고 그 결과를 다시 number_stack에 집어 넣는다.
  • operator가 현재 우선 순위에 해당하는 연산자가 아닌 경우: 그냥 각각의 stack에 넣는다.
• 이제 우선 순위 연산자에 해당하는 연산을 수행한 결과인 number_stack과 operator_stack을 numbers와 operators에 덮어쓰고 그 다음 우선 순위의 연산자로 넘어간다.
• 마지막 우선 순위의 연산자까지 반복한다.

위 과정을 거쳐서 나온 numbers에는 계산한 결과값이 담겨있는데 이 값의 절대값을 최종 결과값과 비교하여 더 큰 수로 교체한다.

모든 순열을 위의 과정을 통해서 확인하면 수식의 최대값을 얻을 수 있다.

from collections import deque
from itertools import permutations
import re


def solution(expression):
    result = 0
    for operator_order in permutations(['*', '+', '-']):
        numbers = deque([int(number) for number in re.findall('[0-9]+', expression)])
        operators = deque(re.findall('[\W]+', expression))

        for priority_operator in operator_order:
            numbers, operators = operate_to_priority_operator(priority_operator, numbers, operators)

        result = max(result, abs(numbers[0]))

    return result


def operate_to_priority_operator(priority_operator, numbers, operators):
    number_stack = deque()
    operator_stack = deque()
    number_stack.append(numbers.popleft())

    while operators:
        now_number = numbers.popleft()
        now_operator = operators.popleft()

        if now_operator == priority_operator:
            operated_number = operate(priority_operator, number_stack.pop(), now_number)
            number_stack.append(operated_number)
            continue

        number_stack.append(now_number)
        operator_stack.append(now_operator)

    return number_stack, operator_stack


def operate(operator, num1, num2):
    if operator == '*':
        return num1*num2
    if operator == '+':
        return num1+num2
    if operator == '-':
        return num1-num2