[프로그래머스] 수식 최대화(Java) - 완전탐색

📌 핵심 요약

• 완전탐색 — 연산자 3개의 우선순위 순열은 6가지뿐이라 전부 시도해도 충분하다
• 토큰 리스트 축약 — 우선순위가 높은 연산자부터 찾아 [숫자, 연산자, 숫자] 세 토큰을 결과 하나로 접는다
• 인덱스 보정 — 리스트를 순회하면서 동시에 수정할 때는 줄어든 크기만큼 인덱스를 되돌려야 한다

 

목차

1 문제 이해

Programmers #67257

수식 최대화

expression 길이 ≤ 100 · 피연산자는 3자리 이하

난이도: Lv.2

+, -, * 세 연산자로 이루어진 수식이 주어진다. 연산자 우선순위를 마음대로 재정의할 수 있을 때(단, 우선순위가 같은 연산자는 없음), 수식 결과의 절댓값이 최대가 되는 값을 구하는 문제다.

풀이 과정

1. 수식을 숫자와 연산자 토큰으로 분리한다
2. 우선순위 순열 6가지를 하나씩 시도한다
3. 각 순열에서 우선순위가 높은 연산자부터 리스트를 훑으며 계산하고, 세 토큰을 결과 하나로 접는다
4. 최종 결과의 절댓값 중 최댓값을 갱신한다

2 접근 방식

연산자가 +, -, * 세 개뿐이라 우선순위 순열은 3! = 6가지밖에 없다.

expression 길이도 최대 100이라서 6가지를 전부 시도하는 완전탐색으로 충분하다고 판단했다.

토큰 분리는 StringTokenizer의 세 번째 인자를 true로 주면 구분자인 연산자까지 토큰으로 같이 뽑아준다.

이러면 정규식 없이 [100, -, 200, *, 300, ...] 형태의 리스트를 바로 만들 수 있다.

계산은 우선순위가 높은 연산자부터 리스트를 앞에서부터 훑으면서, 해당 연산자를 만나면 양옆 숫자와 함께 세 토큰을 지우고 계산 결과 하나를 그 자리에 넣는 방식이다.

ℹ️

중간 결과는 long으로

곱셈이 먼저 처리되는 순열에서는 중간 결과가 int 범위를 넘을 수 있다. 리스트에 문자열로 다시 넣은 중간 결과를 꺼낼 때 Integer.parseInt가 아니라 Long.parseLong으로 읽어야 한다.

3 헤맨 부분: 순회 중 리스트 수정

처음 제출한 코드는 일부 케이스에서 틀렸다.

원인은 리스트에서 토큰 3개를 지우고 1개를 넣으면 리스트가 2칸 줄어드는데, 반복문 인덱스 i는 그대로 i++로 진행된다는 점이었다.

1 - 2 - 3처럼 같은 연산자가 연속으로 나오는 경우를 직접 따라가 보면 문제가 보인다.

 

trace — 보정 없이 실행했을 때

// copy = [1, -, 2, -, 3],  op = "-"
i=1: "-" 매치 → 1-2 계산 → copy = [-1, -, 3]
i=2: copy.get(2) = "3" → 연산자가 아님
i=3: 루프 종료
// 두 번째 "-"는 인덱스 1로 당겨졌는데 i는 이미 2를 지나 건너뛰었다

축약 후 리스트가 2칸 줄었으니 인덱스도 그만큼 되돌려야 한다.

축약 처리 끝에 i--를 넣으면 루프의 i++와 합쳐져 결과적으로 i - 1, 즉 방금 넣은 결과 바로 다음 위치부터 다시 검사하게 된다.

⚠️

순회 중 수정 시 인덱스 보정

리스트를 순회하면서 동시에 요소를 지우거나 넣을 때는, 크기가 변한 만큼 인덱스를 보정해야 한다. 보정을 빼먹으면 같은 요소가 연속으로 나오는 케이스에서만 조용히 틀리기 때문에 원인을 찾기 어렵다.

4 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    private static final String[][] PRIORITIES = {
        {"+", "-", "*"}, {"+", "*", "-"},
        {"-", "+", "*"}, {"-", "*", "+"},
        {"*", "+", "-"}, {"*", "-", "+"}
    };

    public long solution(String expression) {
        // 숫자와 연산자를 토큰으로 분리
        List<String> tokens = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(expression, "+-*", true);
        while (st.hasMoreTokens()) {
            tokens.add(st.nextToken());
        }

        long answer = 0;
        for (String[] priority : PRIORITIES) {
            List<String> copy = new ArrayList<>(tokens);

            for (String op : priority) {
                for (int i = 0; i < copy.size(); i++) {
                    if (op.equals(copy.get(i))) {
                        long left = Long.parseLong(copy.get(i - 1));
                        long right = Long.parseLong(copy.get(i + 1));
                        long result = calculate(left, right, op);

                        // [left, op, right] 세 토큰을 result 하나로 접기
                        copy.remove(i - 1);
                        copy.remove(i - 1);
                        copy.remove(i - 1);
                        copy.add(i - 1, String.valueOf(result));
                        i--; // 리스트가 2칸 줄었으니 인덱스 보정
                    }
                }
            }
            answer = Math.max(answer, Math.abs(Long.parseLong(copy.get(0))));
        }
        return answer;
    }

    private long calculate(long a, long b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            default: throw new IllegalArgumentException("알 수 없는 연산자: " + op);
        }
    }
}

우선순위 순열마다 원본 토큰의 복사본을 만들어 계산하고, 최종적으로 남은 값의 절댓값 중 최댓값을 반환한다.

calculate의 default에서 예외를 던지도록 한 건, 여기 도달하면 로직에 버그가 있다는 뜻이라 조용히 0을 반환하는 것보다 바로 드러나는 편이 낫기 때문이다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.