[프로그래머스] 수식 최대화

문제 요약

숫자와 연산자 +, -, *로만 구성된 수식이 주어진다.

등장한 연산자들의 우선순위를 모두 다르게 정할 수 있을 때, 계산 결과의 절댓값이 가장 커지는 값을 반환한다.

연산자 종류는 최대 세 개이므로 가능한 우선순위는 최대 3! = 6개다.

핵심 아이디어

우선순위 하나를 정하면, 높은 우선순위의 연산자부터 수식 전체에서 계산하면 된다.

예를 들어 우선순위가 ["*", "+", "-"]라면 다음 순서로 처리한다.

1. 모든 * 연산을 계산한다.
2. 남은 수식에서 모든 + 연산을 계산한다.
3. 남은 - 연산을 계산한다.

어떤 연산자를 처리할 때 숫자 목록과 연산자 목록을 따로 관리할 필요는 없다. 숫자, 연산자, 숫자, ... 형태의 토큰 목록을 왼쪽부터 확인하면서, 현재 우선순위의 연산을 발견하면 앞 숫자와 뒤 숫자를 계산해 하나의 숫자로 합치면 된다.

풀이 과정

1. 정규 표현식으로 수식에서 숫자와 연산자를 분리한다.
2. 실제로 등장한 연산자만 모은다.
3. 연산자 우선순위의 모든 순열을 만든다.
4. 각 순열마다 높은 우선순위 연산자부터 토큰 목록을 줄여 간다.
5. 계산 결과의 절댓값 최댓값을 반환한다.

Python 코드

import re
from itertools import permutations


def calculate(left, operator, right):
    if operator == "+":
        return left + right
    if operator == "-":
        return left - right
    return left * right


def solution(expression):
    # 숫자는 int로, 연산자는 문자열로 저장한다.
    tokens = [
        int(token) if token.isdigit() else token
        for token in re.findall(r"\d+|[+*-]", expression)
    ]

    operators = {token for token in tokens if isinstance(token, str)}
    answer = 0

    # 순열의 앞 원소를 가장 높은 우선순위로 사용한다.
    for priority in permutations(operators):
        current = tokens[:]

        for target_operator in priority:
            reduced = [current[0]]

            # 현재 토큰은 항상 숫자, 연산자, 숫자 순서다.
            for index in range(1, len(current), 2):
                operator = current[index]
                right = current[index + 1]

                if operator == target_operator:
                    reduced[-1] = calculate(
                        reduced[-1],
                        operator,
                        right
                    )
                else:
                    reduced.extend([operator, right])

            current = reduced

        answer = max(answer, abs(current[0]))

    return answer

코드 설명

current은 아직 계산하지 않은 수식 토큰이다.

100 - 200 * 300 - 500 + 20

*를 먼저 처리하면 다음처럼 바뀐다.

100 - 60000 - 500 + 20

한 우선순위의 연산자를 모두 처리한 뒤 current = reduced로 갱신한다. 이후 다음 우선순위 연산자도 같은 방식으로 처리한다.

각 우선순위 조합은 독립적으로 계산해야 하므로, current = tokens[:]로 원본 토큰 목록을 복사한다.

예시

expression = "100-200*300-500+20"에서 우선순위를 ["*", "+", "-"]로 정하면 다음과 같다.

100 - 200 * 300 - 500 + 20
100 - 60000 - 500 + 20
100 - 60000 - 520
-60420

절댓값은 60420이다. 모든 우선순위를 확인했을 때 가장 큰 절댓값도 60420이므로 반환값은 60420이다.

시간 복잡도

N을 수식 토큰 개수, K를 등장한 연산자 종류 수라고 하자.

• 우선순위 경우의 수: K!
• 한 우선순위에서 수식 계산: O(K * N)

K는 최대 3이므로, 최대 6개의 우선순위만 확인한다.

• 시간 복잡도: O(K! * K * N)
• 공간 복잡도: O(N)

정리

연산자 우선순위 조합 수가 매우 작으므로 완전 탐색이 적절하다. 핵심은 각 우선순위마다 원본 토큰을 복사하고, 높은 우선순위 연산부터 수식을 차례로 줄여 가는 것이다.