참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요. 대회 규칙에 따라 + > - > x 또는 - > x > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +, x > - 또는 x > +, - 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
expression | result |
---|---|
"100-200*300-500+20" | 60420 |
x > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200x300-500+20
= 100-(200x300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.
현재 계산 우선순위인 연산자가 수식에 있을 때 계산을 하고 수식을 업데이트 하는 부분을 짜는 데 생각보다 오랜 시간이 걸렸다.
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)