문제 24 - [카카오 인턴] 수식 최대화 (Python)

프로그래머스

연산자 +, -, *의 우선순위를 바꿔가며 수식을 계산하고, 그 결과의 절댓값 중 최댓값을 구하는 문제입니다.
핵심은 3! = 6가지 우선순위를 모두 탐색하고, 각 우선순위에 맞게 수식을 직접 계산하는 것입니다.

---

1.  나의 풀이

import re
from itertools import permutations


def apply_operator(tokens, op):
    result = []
    i = 0

    while i < len(tokens):
        if tokens[i] == op:
            left = result.pop()
            right = tokens[i + 1]

            if op == '+':
                result.append(left + right)
            elif op == '-':
                result.append(left - right)
            else:
                result.append(left * right)

            i += 2
        else:
            result.append(tokens[i])
            i += 1

    return result


def solution(expression):
    raw_tokens = re.findall(r'\d+|[+\-*]', expression)

    tokens = []
    for token in raw_tokens:
        if token.isdigit():
            tokens.append(int(token))
        else:
            tokens.append(token)

    answer = 0

    for priority in permutations(['+', '-', '*']):
        temp = tokens[:]

        for op in priority:
            temp = apply_operator(temp, op)

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

    return answer

 

---

2.  오늘 배운 점 및 복기 노트

완전탐색 가능성 판단

연산자는 +, -, * 세 개뿐이므로 가능한 우선순위는 \(3! = 6\)가지입니다.
수식 길이도 최대 100이기 때문에 모든 우선순위를 직접 계산해도 충분합니다.

이 문제는 최적화보다 먼저 “전부 해봐도 되는가”를 판단하는 것이 중요했습니다.

---

정규표현식으로 수식 토큰화하기

re.findall(r'\d+|[+\-*]', expression)

 

이 정규식은 숫자 덩어리 또는 연산자 하나를 뽑아냅니다.

\d+       숫자가 1개 이상 이어진 덩어리
|         또는
[+\-*]    +, -, * 중 하나

 

예를 들어 다음 수식은:

"100-200*300-500+20"

 

다음처럼 분리됩니다.

['100', '-', '200', '*', '300', '-', '500', '+', '20']

 

여기서 \d+를 사용해야 100이 하나의 숫자 덩어리로 잡힙니다.

---

리스트를 좁혀나가는 계산 방식

나의 풀이는 우선순위가 높은 연산자부터 계산하면서 리스트를 줄여나가는 방식입니다.

[100, '-', 200, '*', 300, '-', 500, '+', 20]

 

우선순위가 *, +, -라면 먼저 *를 처리합니다.

[100, '-', 60000, '-', 500, '+', 20]

 

그다음 +를 처리합니다.

[100, '-', 60000, '-', 520]

 

마지막으로 -를 처리합니다.

[-60420]

 

이 문제처럼 입력이 작고 연산자 종류가 적을 때는 이 방식이 직관적이고 충분히 효율적입니다.

---

왼쪽 피연산자는 result.pop()으로 꺼내기

특정 연산자를 만났을 때 왼쪽 피연산자는 이미 result에 들어 있습니다.

left = result.pop()
right = tokens[i + 1]

 

이후 연산자와 오른쪽 피연산자를 함께 소비하므로 인덱스를 2 증가시킵니다.

i += 2

 

이 부분이 처음에는 헷갈릴 수 있지만, 핵심은 “현재 연산자의 왼쪽 값은 이미 결과 리스트에 들어 있다”는 점입니다.

---

뺄셈은 피연산자 순서가 중요함

덧셈과 곱셈은 순서를 바꿔도 되지만, 뺄셈은 순서가 바뀌면 결과가 달라집니다.

left - right

 

따라서 리스트 축소 방식에서도, 후위 표기식 계산에서도 왼쪽 값과 오른쪽 값을 정확히 구분해야 합니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

수식 계산 문제는 표기법 변환으로 풀 수 있음

교재에서는 중위 표기식을 후위 표기식으로 바꾼 뒤 스택으로 계산하는 방법을 소개합니다.

중위 표기식은 우리가 일반적으로 쓰는 방식입니다.

50 * 6 - 3 * 2

 

후위 표기식은 연산자가 뒤에 오는 방식입니다.

50 6 * 3 2 * -

 

후위 표기식에는 계산 순서가 이미 반영되어 있습니다.
따라서 계산할 때는 더 이상 연산자 우선순위를 따질 필요가 없습니다.

---

후위 표기식 계산 방식

후위 표기식은 스택으로 계산합니다.

숫자면 스택에 넣습니다.
연산자면 숫자 두 개를 꺼냅니다.
계산 결과를 다시 스택에 넣습니다.
마지막에 남은 값이 결과입니다.

 

예를 들어:

50 6 3 - * 2 *

 

계산 순서는 다음과 같습니다.

6 - 3 = 3
50 * 3 = 150
150 * 2 = 300

 

즉, 이 후위 표기식은 다음 중위 표기식과 같습니다.

50 * (6 - 3) * 2

 

---

중위를 후위로 바꿀 때의 핵심

중위 표기식을 후위 표기식으로 바꿀 때는 연산자 스택을 사용합니다.

숫자는 바로 결과 리스트에 넣습니다.
연산자는 스택에 넣습니다.
스택 위 연산자가 현재 연산자보다 먼저 계산되어야 하면 꺼냅니다.
입력을 다 읽으면 스택에 남은 연산자를 모두 꺼냅니다.

 

핵심 조건은 다음입니다.

while operator and priority_dict[operator[-1]] >= priority_dict[token]:
    post_order.append(operator.pop())

 

이 조건은 “스택 위 연산자가 현재 연산자보다 우선순위가 높거나 같으면 먼저 계산되어야 한다”는 뜻입니다.

---

후위 표기식 변환 코드

def to_postfix(tokens, priority):
    priority_dict = dict(zip(priority, [3, 2, 1]))

    operator = []
    post_order = []

    for token in tokens:
        if isinstance(token, int):
            post_order.append(token)
        else:
            while operator and priority_dict[operator[-1]] >= priority_dict[token]:
                post_order.append(operator.pop())

            operator.append(token)

    while operator:
        post_order.append(operator.pop())

    return post_order

 

여기서는 priority의 앞쪽 연산자가 더 높은 우선순위를 가진다고 가정했습니다.

priority = ('*', '+', '-')

 

이면 실제 우선순위는 다음과 같습니다.

* > + > -

 

---

후위 표기식 계산 코드

def calc_postfix(postfix):
    stack = []

    for token in postfix:
        if isinstance(token, int):
            stack.append(token)
        else:
            right = stack.pop()
            left = stack.pop()

            if token == '+':
                stack.append(left + right)
            elif token == '-':
                stack.append(left - right)
            else:
                stack.append(left * right)

    return stack[0]

 

여기서 먼저 pop()한 값이 오른쪽 피연산자입니다.

right = stack.pop()
left = stack.pop()

 

따라서 뺄셈은 반드시 다음처럼 계산해야 합니다.

left - right

 

---

리스트 축소 방식과 후위 표기식 방식의 차이

구분리스트 축소 방식후위 표기식 방식

핵심	우선순위 높은 연산자부터 직접 계산	우선순위를 반영한 식으로 변환
자료구조	리스트	스택
구현 난이도	낮은 편	높은 편
이 문제 적합성	매우 적합	정석적인 수식 계산 방식
확장성	제한적	높음

이 문제는 괄호가 없고 연산자도 세 개뿐이므로 리스트 축소 방식이 충분히 좋습니다.
하지만 괄호가 있거나 연산자 종류가 많아지면 후위 표기식을 떠올리는 것이 좋습니다.