[프로그래머스] [카카오 인턴] 수식 최대화

작성일: 2024-11-21

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/67257

접근 방식

수식이 주어지고, 연산자의 우선순위를 통한 최대값을 구해야 하기 때문에 순열을 이용해야 한다.

순열을 이용해서 연산자의 우선순위를 정해서, 계산을 모두 진행한 뒤 최댓값을 구하면 된다.

잘못된 접근

한 번에 순열 결과값을 구하고, 그걸로 연산을 진행해서 최댓값을 구하려다보니 쉽지 않았다.

결과

소스 코드

import java.util.*;

class Solution {
    static long answer = 0;
    public long solution(String expression) {
        List<Long> nums = new ArrayList<>();
        List<Character> ops = new ArrayList<>();
        Set<Character> opSet = new HashSet<>(); // 사용된 연산자들

        // 1. 숫자와 연산자 분리
        StringBuilder numBuffer = new StringBuilder();
        for (char ch : expression.toCharArray()) {
            if (Character.isDigit(ch)) {
                numBuffer.append(ch);
            } else {
                nums.add(Long.parseLong(numBuffer.toString()));
                numBuffer.setLength(0); // 초기화
                ops.add(ch);
                opSet.add(ch);
            }
        }
        nums.add(Long.parseLong(numBuffer.toString())); // 마지막 숫자 추가

        // 2. 연산자 순열 생성
        List<Character> opList = new ArrayList<>(opSet);
        List<List<Character>> perms = new ArrayList<>();
        perm(opList, new ArrayList<>(), new boolean[opList.size()], perms);

        // 3. 각 우선순위에 대해 계산
        for (List<Character> priority : perms) {
            answer = Math.max(answer, Math.abs(calculate(new ArrayList<>(nums), new ArrayList<>(ops), priority)));
        }

        return answer;
    }

    // 순열 생성
    private void perm(List<Character> opList, List<Character> temp, boolean[] visited, List<List<Character>> result) {
        if (temp.size() == opList.size()) {
            result.add(new ArrayList<>(temp)); // 완성된 순열 추가
            return;
        }
        for (int i = 0; i < opList.size(); i++) {
            if (visited[i]) continue;
            visited[i] = true;
            temp.add(opList.get(i));
            perm(opList, temp, visited, result);
            temp.remove(temp.size() - 1);
            visited[i] = false;
        }
    }


    // 주어진 우선순위에 따라 계산 수행
    private long calculate(List<Long> nums, List<Character> ops, List<Character> priority) {
        for (char op : priority) {
            for (int i = 0; i < ops.size(); ) {
                if (ops.get(i) == op) {
                    long result = operate(nums.get(i), nums.get(i + 1), op);
                    nums.remove(i + 1); // 다음 인덱스 제거
                    nums.set(i, result); // 현재 인덱스 값 수정
                    ops.remove(i); // 연산자 제거
                } else {
                    i++; // 계산해야 할 연산자가 아니라면 넘어가기
                }
            }
        }
        return nums.get(0); // 최종 계산 결과
    }

    // 두 숫자와 연산자를 받아 계산
    private long operate(long a, long b, char op) {
        if(op=='+'){
            return a+b;
        }else if(op=='-'){
            return a-b;
        }else{
            return a*b;
        }
    }
}

크게 세 가지의 로직으로 나뉘어져있다.

문자열에서, 숫자와 연산자를 분리해서 저장하기.
저장된 연산자를 이용한 순열을 생성해서 모든 경우의 수에 대비하기.
만들어진 순열을 바탕으로 하나씩 경우의 수를 계산해가며 최댓값을 갱신하기.

알게 된 점

일반적으로 잘 사용되지 않기 때문에 놓치기 쉬웠던 부분이 있었다.
바로 List사용, 리스트는 참조형 객체이기 때문에 리스트에 담긴 값을 이용할 때, 변경된 값이 추가되어 원래의 값을 훼손시킬 우려가 있다.

따라서 참조형 객체(String, 배열 등)를 사용하는 경우 새로운 객체를 만들어서 해당 객체에 담아서 사용할 수 있도록 해야 한다!!!