프로그래머스 Lv2 수식 최대화

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

문제를 간단히 요약해보면 입력으로 3~100자인 문자열이 들어오는데 이는 0이상 999이하의 숫자와 +, -, * 세 개의 연산자로 이루어진 수식이다.

여기서 연산자 우선 순위를 임의로 바꾸어 계산했을 때, 결과 값의 절댓값이 가장 큰 경우를 구해야한다.

입력으로 "100-200*300-500+20" 이 들어온다면 60420이 출력되어야 한다.
또 "50*6-3*2"가 들어왔을 때는 300이 출력되어야 한다.

풀이

먼저 떠오른 것은 어쨋든 연산자 우선 순위를 바꿔가며 직접 계산해보는 방법 뿐이었다. 연산자가 3개 뿐이라 6가지 경우 뿐이라

expression = ["*+-", "*-+", "+-*", "+*-", "-*+", "-+*"]

이렇게 써놓고 쓰려다가 괜히 백트래킹으로 하면 있어보일 것 같아서 백트래킹으로 했다;;

연산자 우선 순위를 정해줄 함수를 만들고, 이 함수에서 우선 순위가 모두 정해지는 순간에는 또 다시 그 우선 순위대로 계산을 해주는 함수를 호출해 결과 값을 처리하는 식으로 해결했다.

계산은 또 어떻게 해야할지 고민을 했는데, 연산자 우선 순위는 정해졌으니 식을 가장 우선 순위가 높은 연산자를 기준으로 split해주며 재귀 호출하는 식으로 계산해주었다. 뭔가 썩 이쁜 코드는 아닌 느낌이지만 어쨋든 해결되었다. 이럴땐 재귀가 참 편리하다.

check = [0, 0, 0]
exp = {0:"*", 1:"+", 2:"-"}
answer = 0
def solution(expression):
    prioritize(0, "", expression)
    return answer

def prioritize(n, ex, expression): #연산자 우선순위 정하기
    global answer
    if n == 3:
        result = abs(calculate(ex, expression))
        if answer < result:
            answer = result
        return
            
    for i in range(3):
        if check[i] == 0:
            check[i] = 1
            prioritize(n+1, ex+exp[i], expression)
            check[i] = 0
            
def calculate(ex, expression):	#계산하기
    if ex == "":
        return int(expression)
    
    splited = expression.split(ex[0])
    result = calculate(ex[1:], splited[0]) 
    for s in splited[1:]:
        if ex[0] == "*":
            result *= calculate(ex[1:], s)
        elif ex[0] == "+":
            result += calculate(ex[1:], s)
        elif ex[0] == "-":
            result -= calculate(ex[1:], s)
    return result