악곱 == 악성곱슬

재귀(트리), 순열

---

이 문제는 연산자의 우선순위를 정해서 연산을 했을 경우 최댓값을 도출하는 문제이다. 연산의 종류는 총 3가지이다.

따라서 모든 조합의 경우의 수를 고려해도 6가지밖에 나오지 않는다. 따라서 permutations를 부담없이 사용해도 된다.

그리고 split을 우선순위의 역순으로 사용하며 재귀를 통해 연산을 이어나간다. try-except 구문을 이용하여 int로 형변환을 하고 에러가 발생한다면 아직 연산자가 남았다는 뜻으로 재귀를 이어나간다. 코드는 아래와 같다.

구현

---

from itertools import permutations

def recursion(expression, ops, depth):
    tmp_lst = expression.split(ops[depth])
    # 초기 값 설정
    try:
        answer = int(tmp_lst[0])
    except:
        answer = recursion(tmp_lst[0], ops, depth+1)
    # 계산
    for i in range(1, len(tmp_lst)):
        try:
            value = int(tmp_lst[i])
        except:
            value = recursion(tmp_lst[i], ops, depth+1)
        if ops[depth] == "*":
            answer *= value
        elif ops[depth] == "-":
            answer -= value
        elif ops[depth] == "+":
            answer += value
    return answer

def solution(expression):
    operators = ['*', '-', '+']
    priority = list(permutations(operators, 3))
    answer = 0
    for op in priority:
        answer = max(answer, abs(recursion(expression, op, 0)))
    return answer

print(solution("100-200*300-500+20"))
print(solution("50*6-3*2"))