백준 - 14888 - 연산자 끼워넣기

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

import java.util.*;

/**
 * 백준 14888
 */
public class 연산자_끼워넣기 {
    private static int min = Integer.MAX_VALUE;
    private static int max = Integer.MIN_VALUE;
    private static int[] countOperators;
    private static int[] numbers;
    private static int[] operators;
    private static boolean[] isUsed;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        numbers = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        countOperators = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        makeOperators();
        isUsed = new boolean[operators.length];

        findMaxAndMin(N-1, new ArrayList<>());
        System.out.println(max);
        System.out.println(min);
    }

    private static void findMaxAndMin(int depth, List<Integer> result) {
        //종료
        if(depth == 0) {
            int calRes = numbers[0];
            for(int i=1; i<numbers.length; i++) {
                calRes = operate(calRes, numbers[i], result.get(i-1));

            }
            max = Math.max(max, calRes);
            min = Math.min(min, calRes);
            return;
        }

        //프로세스
        for(int i=0; i<operators.length; i++) {
            if(!isUsed[i]) {
                isUsed[i] = true;
                result.add(operators[i]);
                findMaxAndMin(depth-1, result);
                result.remove(result.size()-1);
                isUsed[i] = false;
            }
        }
    }

    /**
     * 연산자 갯수만큼 연산자를 만들어줌
     * + -> 0, - -> 1, * -> 2, / -> 3
     * 시간 복잡도: O(N)
     */
    private static void makeOperators() {
        operators = new int[countOperators[0]+countOperators[1]+countOperators[2]+countOperators[3]];
        int operatorIndex = 0;
        for(int i=0; i<countOperators.length; i++) {
            for(int j=0; j<countOperators[i]; j++) {
                operators[operatorIndex++] = i;
            }
        }
    }

    private static int operate(int num1, int num2, int operator) {
        switch (operator) {
            case 0: return num1 + num2;
            case 1: return num1 - num2;
            case 2: return num1 * num2;
            default: return num1 / num2;
        }
    }
}

알고리즘

• 백트래킹, 순열
• 입력받은 연산자의 갯수에 따라 연산자 배열을 만들어준다(꼭 필요한 로직은 아니지만 문제를 단순화 시키기 위함)
• 연산자 배열의 순열을 만들어준다(위치 중복제거 순열)
• 만들어진 순열과 입력받은 숫자들의 연산을 통해 최대값과 최소값을 구한다.