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

2020 카카오 인턴십 - 67257. 수식 최대화

Python 풀이

 

풀이

우선, 이런 중위 표현식, 후위 표현식, 연산자 우선순위에 관한 문제들을 숱히 Stack으로 풀어 왔기에,

Stack을 이용해 풀이해 보자 - 라고 생각했으나,

굳이 그럴 필요 없을 것 같아서 간단하게 생각하여 풀이했다.

 

우선순위 경우의 수가 최대 6가지밖에 없으니, 6가지 경우의 수를 모두 따져 보아 계산한다.

만약, 우선순위가 ['*', '-', '+'] 라면,

'*' 를 모두 찾아 앞뒤로 계산 후 다시 그 index쪽에 집어넣고,

그 다음 '-' 도 같은 방법으로.

마지막으로 '+' 도 같은 방법으로 계산.

 

예를 들어, 아래와 같다면,

expression = "100-200*300-500+20"
우선순위 = ['*', '+', '-']

계산 과정은 아래와 같을 것.

[100, '-', 200, '*', 300, '-', 500, '+', 20]
[100, '-', 60000, '-', 500, '+', 20]
[100, '-', 60000, '-', 520]
[-59900, '-', 520]
[-60420]

 

 

Code

from collections import deque

def solution(expression):
    expression = deque(expression)
    num = ""
    ex = []

    while expression:
        a = expression.popleft()
        if a in ["-", "*", "+"]:
            ex.append(int(num))
            ex.append(a)
            num = ""
        else:
            num += a

    ex.append(int(num))

    priority = [['+', '-', '*'], ['+', '*', '-'], ['-', '+', '*'],
                ['-', '*', '+'], ['*', '-', '+'], ['*', '+', '-']]


    def cal(oper, x, y):
        if oper == '+':
            return x+y
        elif oper == '-':
            return x-y
        else:
            return x*y


    answer = []

    for prior in priority:
        prior = deque(prior)
        exp = ex[:]
        for _ in range(3):
            op = prior.popleft()
            while op in exp:
                i = exp.index(op)
                an = cal(op, exp[i-1], exp[i+1])
                exp[i-1:i+2] = []
                exp.insert(i-1, an)

        answer.append(abs(int(exp[0])))

    return max(answer)