수식 최대화 (Level 2)

문제

 

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

코딩테스트 연습 - 수식 최대화

 

내 풀이

 

permutations를 사용해서 (+, -, *)로 만들 수 있는 모든 우선순위 조합인 9가지 경우의 수를 구하였다.

그리고 수식에서 숫자와 연산자를 분리하여 리스트에 넣었다. ex) ['100', '+', '200', '-', '50', '*', '2']

9가지 우선순위 조합에 해당하는 연산 값을 각각 구하였다.

값을 구할 때 stack을 사용한 것이 핵심이다.

 

from itertools import permutations

def add(a, b): return a+b
def sub(a, b): return a-b
def mul(a, b): return a*b

def solution(expression):
    operators = list(permutations('+-*'))   
    cal = {'+': add, '-': sub, '*': mul}
    lst = []
    tmp = ''
    for exp in expression:
        if exp.isdigit():
            tmp += exp
        else:
            lst.append(tmp)
            tmp = ''
            lst.append(exp)
    lst.append(tmp)
    MAX = 0
    for operator in operators:
        lst_c = lst[:]
        for op in operator:
            stack = []
            flag = True
            for i, comp in enumerate(lst_c):
                if not flag:
                    flag = True
                    continue
                elif comp != op:
                    stack.append(comp)
                elif comp == op:
                    first = stack.pop()
                    second = lst_c[i+1]
                    stack.append(cal[op](int(first), int(second)))
                    flag = False
            lst_c = stack[:]
        MAX = max(MAX, abs(int(stack[0])))
    return MAX

 

과거의 내 풀이

from itertools import permutations
import math

def solution(expression):
    lst = []
    tmp = ''
    for exp in expression:
        if exp == '-' or exp == '*' or exp == '+':
            lst.append(int(tmp))
            lst.append(exp)
            tmp = ''
        else:
            tmp += exp
    lst.append(int(tmp))

    postfix, op = [], []
    pool = ['*', '+', '-']
    permu = list(permutations(pool))
    MAX = -math.inf
    for p in permu:
        priority = {}
        priority[p[0]], priority[p[1]], priority[p[2]] = 1, 2, 3

        for l in lst:
            if l != '-' and l != '*' and l != '+':
                postfix.append(l)
            else:
                if not op:
                    op.append(l)
                else:
                    if priority[op[-1]] <= priority[l]:
                        while op and priority[op[-1]] <= priority[l]:
                            postfix.append(op.pop())
                        op.append(l)
                    else:
                        op.append(l)
        while op:
            postfix.append(op.pop())

        operand = []
        for p in postfix:
            if p == '*':
                operand.append(operand.pop() * operand.pop())
            elif p == '+':
                operand.append(operand.pop() + operand.pop())
            elif p == '-':
                fst = operand.pop()
                snd = operand.pop()
                operand.append(snd - fst)
            else:
                operand.append(p)
        MAX = max(MAX, abs(operand[-1]))

    return MAX

 

총평

다른 풀이는 eval 함수 같은 치트키를 좀 쓴 것 같아서 마음에 들지 않았다. 그래서 최대한 내 힘으로 풀어야겠다고 생각했다. 과거에 풀었던 것과 비교하면 확실히 풀이가 짧아지고 깔끔해진 것 같다. 조금이라도 발전된 것 같아서 좋다.