연습

수식 최대화

프로그래머스 67257

갱신

2026-10-02

문제 보기 · Level 2 · 2020 카카오 인턴십 · 정답률 49% · 푼 사람 15,925명 (2026-09-30 기준)¹

문제

숫자와 +, −, *로 된 수식이 주어진다. 세 연산자의 우선순위를 서로 다르게 새로 정해 계산하고, 결과의 절댓값을 상금으로 받는다. 받을 수 있는 가장 큰 상금을 돌려준다. 같은 연산자끼리는 앞에 있는 것부터 계산한다.

• 수식 길이 3~100
• 피연산자 0~999
• 중간값과 결과의 절댓값은 \(2^{63}-1\) 이하

풀이

막히면 한 단계씩 펼친다.

필요한 개념

• 완전탐색: 연산자 우선순위 순서를 모두 만들어 본다(permutations).
• 문자열 파싱과 정규 표현식: 수식을 숫자와 연산자로 자르기.

1단계 · 작은 예로 손으로 풀기

“2-3*4”에 쓰인 연산자는 −와 * 두 개라 순서는 두 가지다.

• *가 먼저: 2 − (3 × 4) = −10 → 절댓값 10
• −가 먼저: (2 − 3) × 4 = −4 → 절댓값 4

답은 10이다. 음수가 나와도 절댓값으로 바꾸니 크게 음수가 되는 순서도 좋은 후보다.

2단계 · 가장 단순한 방법과 그 속도

연산자는 많아야 세 종류라 우선순위 순서는 3! = 6가지뿐이다. 세 연산자를 한 줄로 세우는 순열의 수다. 순서마다 수식을 한 번 계산하면(길이 100) 모두 600번 정도다. 모두 해 보면 된다.

3단계 · 핵심 아이디어

1. 자르기: re.split(r"([+\-*])", 수식)은 연산자를 기준으로 자르되, 괄호로 묶은 연산자도 결과에 남긴다. "100-200*300" → ['100', '-', '200', '*', '300']. 짝수 번째는 숫자, 홀수 번째는 연산자다.
2. 한 연산자씩 계산: 우선순위가 높은 연산자부터 하나씩, 목록을 왼쪽부터 훑으며 그 연산자가 나오면 바로 앞 숫자와 뒤 숫자를 계산해 하나로 합친다. 그 연산자가 목록에서 사라지면 다음 연산자로 간다. 왼쪽부터 훑으니 “같은 연산자는 앞부터”가 저절로 지켜진다.
3. 최대: 순서마다 결과의 절댓값을 구해 가장 큰 것을 고른다.

4단계 · 코드 흐름

1. 수식을 숫자·연산자 목록으로 자르고, 숫자는 정수로 바꾼다.
2. 수식에 나온 연산자들의 모든 순서마다:
   • 목록을 복사한다.
   • 순서대로 연산자 하나씩, 목록을 훑으며 그 연산자를 계산해 줄인다.
   • 남은 숫자 하나의 절댓값으로 최댓값을 고친다.
3. 최댓값을 돌려준다.

5단계 · 파이썬 코드

import re
from itertools import permutations

def solution(expression):
    tokens = re.split(r"([+\-*])", expression)
    tokens = [int(t) if t.isdigit() else t for t in tokens]   # 숫자는 정수로
    calc = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b}

    best = 0
    for order in permutations(set(tokens[1::2])):              # 나온 연산자들의 순서
        t = tokens[:]
        for op in order:                                       # 우선순위가 높은 것부터
            out = [t[0]]
            for i in range(1, len(t), 2):                      # (연산자, 숫자)씩
                if t[i] == op:
                    out[-1] = calc[op](out[-1], t[i + 1])      # 앞 숫자와 합친다
                else:
                    out += [t[i], t[i + 1]]
            t = out
        best = max(best, abs(t[0]))
    return best

• tokens[1::2]: 1번부터 두 칸씩, 즉 연산자만 고른다. set으로 겹침을 없앤다.
• calc: 연산자 글자를 계산 함수로 바꾸는 딕셔너리다. lambda a, b: a + b는 이름 없는 두 줄짜리 함수를 한 줄로 쓴 것이다.
• out[-1] = calc[op](out[-1], t[i + 1]): 결과 목록의 마지막 숫자와 다음 숫자를 계산해 그 자리에 둔다. 그래서 1-2-3은 (1−2)−3 = −4가 된다.

6단계 · 실행 추적

“506-32”, 연산자는 *와 −

순서	계산	결과	절댓값
* → −	300 − 6	294	294
− → *	50 × (6 − 3) × 2	300	300

답은 300이다.

7단계 · 복잡도와 흔한 실수

순서 최대 6가지 × 연산자마다 목록 한 번 훑기 × 연산자 3종류라 수식 길이 L에 대해 \(O(L)\)이다.

• 같은 연산자를 오른쪽부터 계산해 1−2−3을 1−(2−3) = 2로 만든다.
• 절댓값을 빼먹는다.
• 수식에 없는 연산자까지 순서에 넣는다. 결과는 같지만 불필요하게 두 배 넘게 돈다.

검증: 문제의 예시 2개를 통과했고, 무작위 수식 3,000개에서 “가장 낮은 우선순위 연산자로 수식을 나눠 부분식을 재귀로 계산하고 왼쪽부터 합치는” 다른 풀이와 결과가 같았다 — 16_pg67257_p1.py

1. 프로그래머스 스쿨, “수식 최대화” (https://school.programmers.co.kr/learn/courses/30/lessons/67257), 2026-09-30 조회. ↩