[프로그래머스/Java] Lv.2 - 수식 최대화

승래·2026년 3월 27일

프로그래머스 Lv.2 - 수식 최대화

요구사항

숫자와 +, -, * 연산자로 이루어진 수식이 주어질 때
연산자 우선순위를 마음대로 정해서 만들 수 있는 결과의 최댓값을 구하는 문제
결과의 절댓값이 최대인 값을 반환

접근 방식

DFS로 연산자 우선순위 순열 생성 + 우선순위대로 계산 으로 풀었다.

핵심 아이디어

연산자 종류가 최대 3개 (+, -, *)
→ 우선순위 순열: 최대 3! = 6가지

각 순열마다 우선순위 높은 연산자부터 순서대로 계산
→ 결과의 절댓값 중 최댓값이 정답

구현 순서

1. 문자열 파싱: 숫자 리스트, 연산자 리스트 분리
2. DFS로 연산자 우선순위 순열 생성
3. 각 순열마다 우선순위 높은 연산자부터 계산
   → 계산 후 해당 연산자와 숫자를 리스트에서 제거
4. 절댓값 중 최댓값 갱신

계산 방식

priority = [*, +, -] 일 때
"100-200*300-500+20" 수식에서

1단계: * 먼저 계산
  200*300 = 60000
  → [100, 60000, 500, 20], [-, -, +]

2단계: + 계산
  500+20 = 520 (아니라 -500+20이 아니라 연산자 순서대로)
  ...

3단계: - 계산
  최종 결과

코드

import java.util.*;

class Solution {
    long answer;
    ArrayList<Long> numbers;
    ArrayList<Character> op;

    public long solution(String expression) {
        answer = 0;
        numbers = new ArrayList<>();
        op = new ArrayList<>();

        String number = "";
        for (char c : expression.toCharArray()) {
            if (c == '*' || c == '+' || c == '-') {
                op.add(c);
                numbers.add(Long.parseLong(number));
                number = "";
            } else {
                number += c;
            }
        }
        numbers.add(Long.parseLong(number));

        ArrayList<Character> oper = new ArrayList<>();
        for (char c : op) {
            if (oper.contains(c)) continue;
            oper.add(c);
        }

        boolean[] visit = new boolean[oper.size()];
        ArrayList<Character> priority = new ArrayList<>();
        dfs(0, visit, oper, priority);

        return answer;
    }

    public void dfs(int idx, boolean[] visit, ArrayList<Character> oper, ArrayList<Character> priority) {
        if (idx == oper.size()) {
            calculate(priority);
        } else {
            for (int i = 0; i < oper.size(); i++) {
                if (visit[i]) continue;
                visit[i] = true;
                priority.add(oper.get(i));
                dfs(idx + 1, visit, oper, priority);
                priority.remove(priority.size() - 1);
                visit[i] = false;
            }
        }
    }

    public void calculate(ArrayList<Character> priority) {
        ArrayList<Long> num = new ArrayList<>(numbers);
        ArrayList<Character> o = new ArrayList<>(op);

        for (char c : priority) {
            for (int i = 0; i < o.size(); i++) {
                if (o.get(i) == c) {
                    long result = sum(num.get(i), num.get(i+1), c);
                    num.set(i, result);
                    num.remove(i+1);
                    o.remove(i);
                    i--;
                }
            }
        }
        answer = Math.max(answer, Math.abs(num.get(0)));
    }

    public long sum(long x, long y, char op) {
        if (op == '+') return x + y;
        else if (op == '-') return x - y;
        else return x * y;
    }
}