[프로그래머스] 수식 최대화 / Python / 순열과 조합

수식 최대화

문제

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요. 대회 규칙에 따라 + > - > x 또는 - > x > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +, x > - 또는 x > +, - 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.

• 입출력 예시

x > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200x300-500+20
= 100-(200x300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

• 제한사항
  - expression은 길이가 3 이상 100 이하인 문자열입니다.
  - expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다. 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
  - expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
  - 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

나의 풀이

현재 계산 우선순위인 연산자가 수식에 있을 때 계산을 하고 수식을 업데이트 하는 부분을 짜는 데 생각보다 오랜 시간이 걸렸다.

from itertools import permutations

# 수식에서 연산자와 피연산자 분리
def split_expression(expression):
    operand = ''
    result = []
    for i, x in enumerate(expression):
        # 숫자일 경우
        if x.isdigit():
            operand += x
            if i == len(expression) - 1:
                result.append(operand)
        # 연산자일 경우
        else:
            result.append(operand)
            result.append(x)
            operand = ''
    return result
    
    
def solution(expression):
    ops = ["+", "-", "*"]
    # 연산자 3개의 우선순위 조합
    pm = list(permutations(ops))
    max_value = 0
    for i in range(6):
        exp = split_expression(expression)
        for j in range(3):
            # 현재 우선순위인 연산자가 수식에 있을 때 
            while pm[i][j] in exp:
            	# 연산자의 인덱스를 가져옴
                idx = exp.index(pm[i][j])
                exp = exp[:idx - 1] + [str(eval(''.join(exp[idx - 1:idx + 2])))] + exp[idx + 2:]
        max_value = max(max_value, abs(int(exp[0])))        
    return max_value

상위 풀이

이렇게 간단하게 풀 수 있다니!!

import itertools

def solution(expression):
    symbols = ["-", "+", "*"]
    answer = []
    for i in itertools.permutations(symbols):
        first, second = i[0], i[1]
        lst = []
        for e in expression.split(first):
            temp = [f"({i})" for i in e.split(second)]
            lst.append(f'({second.join(temp)})')
        answer.append(abs(eval(first.join(lst))))
    return max(answer)