백분 알고리즘 - 연산자 끼워넣기

다행히도 연산할 때 우선순위가 없다.
무조건 앞쪽부터 차례대로 연산해서 고려 할게 줄었다.

+-*/ 4가지의 개수를 String 배열에 담았다.
인풋이 2 1 2 1 이면 "+", "+", "-", "*", "*", "/"
그 후 DFS로 끝까지 탐색 할 때마다 연산하고 값을 HashSet에 담았다.
그리고 최소값, 최대값을 출력해 주었다.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

//+ - * /
public class Main {
    private static int max = 0;
    private static int min = 0;
    private static int[] sequence;
    private static String[] operators;
    private static boolean[] isVisit;

    private static String[] resultOp;
    private static HashSet<Integer> resultSet = new HashSet<>();

    private static int[] resultArr = new int[2];

    private static int oIdx = 0;

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int numCnt = Integer.parseInt(scn.nextLine());
        String sequenceStr = scn.nextLine();
        String[] sequencesString = sequenceStr.split(" ");
        sequence = new int[sequencesString.length];
        for (int i = 0; i < numCnt; i++) {
            sequence[i] = Integer.parseInt(sequencesString[i]);
        }

        operators = new String[sequence.length - 1];
        isVisit = new boolean[sequence.length - 1];
        resultOp = new String[sequence.length - 1];

        String operatorStr = scn.nextLine();
        String[] operatorsString = operatorStr.split(" ");

        insertOp("+", operators, Integer.parseInt(operatorsString[0]));
        insertOp("-", operators, Integer.parseInt(operatorsString[1]));
        insertOp("*", operators, Integer.parseInt(operatorsString[2]));
        insertOp("/", operators, Integer.parseInt(operatorsString[3]));

        for (int i = 0; i < operators.length; i++) {
            isVisit[i] = true;
            DFS(operators, isVisit, operators[i], operators.length, 0);
            isVisit[i] = false;
        }
        if (operators.length > 1) {
            Iterator iterator = resultSet.iterator();
            int firstVal = (Integer) iterator.next();
            max = firstVal;
            min = firstVal;
            while (iterator.hasNext()) {
                int thisVal = (Integer) iterator.next();
                if (min > thisVal) {
                    min = thisVal;
                }
                if (max < thisVal) {
                    max = thisVal;
                }
            }
            System.out.println(max);
            System.out.println(min);
        } else {
            System.out.println(resultArr[0]);
            System.out.println(resultArr[1]);
        }
    }
    private static void insertOp(String type, String[] op, int time) {
        for (int i = 0; i < time; i++) {
            op[oIdx] = type;
            oIdx++;
        }
    }
    private static void DFS(String[] op, boolean[] visit, String start, int last, int depth) {
        resultOp[depth] = start;
        if (depth == last - 1) {
            int calculated = sequence[0];
            for (int i = 0; i < last; i++) {
                if (last == 1) {
                    switch (resultOp[i]) {
                        case "+":
                            calculated += sequence[i + 1];
                            break;
                        case "-":
                            calculated -= sequence[i + 1];
                            break;
                        case "*":
                            calculated *= sequence[i + 1];
                            break;
                        case "/":
                            calculated /= sequence[i + 1];
                            break;
                    }
                    resultArr[0] = calculated;
                    resultArr[1] = calculated;
                } else {
                    switch (resultOp[i]) {
                        case "+":
                            calculated += sequence[i + 1];
                            break;
                        case "-":
                            calculated -= sequence[i + 1];
                            break;
                        case "*":
                            calculated *= sequence[i + 1];
                            break;
                        case "/":
                            calculated /= sequence[i + 1];
                            break;
                    }
                }
            }
            resultSet.add(calculated);
        } else {
            for (int i = 0; i < last; i++) {
                if (visit[i])
                    continue;
                visit[i] = true;
                DFS(op, visit, op[i], last, depth + 1);
                visit[i] = false;
            }
        }
    }

}