[이것이 코딩 테스트다 with Python] 연산자 끼워 넣기(Java)

Goal

“이것이 코딩 테스트다 with Python” 교재의 문제를 분석하고 코드와 함께 이해해보기 위한 글입니다.

문제 분석

연산자 우선순위를 무시하고 앞에서부터 진행해야한다고 되어 있기 때문에

1. 크기가 4인 배열에 연산자 갯수를 저장하고,
2. 반복문에서 연산자를 하나씩 재귀호출할 때마다 사용된 연산자의 갯수를 1 감소시켜서
3. 0이 된다면 다음 연산자 계산으로 넘아가는

프로그램을 작성하면 됩니다.

코드 구현

public class InsertingOperators { // p349
    static int[] operator = new int[4];
    static int[] num;
    static int n;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        num = new int[n];

        // 숫자 값 저장
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        // 연산자 갯수 저장
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
        }

        dfs(num[0], 1);
        StringBuilder sb = new StringBuilder();
        sb.append(max).append("\n").append(min).append("\n");
        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    static void dfs(int number, int idx) {
        if (idx == n) {
            max = Math.max(max, number);
            min = Math.min(min, number);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (operator[i] > 0) {
                operator[i]--;
                switch (i) {
                    case 0: dfs(number + num[idx], idx + 1); break;
                    case 1: dfs(number - num[idx], idx + 1); break;
                    case 2: dfs(number *  num[idx], idx + 1); break;
                    case 3: dfs(number / num[idx], idx + 1); break;
                }
                // 재귀호출이 종료되면 다시 해당 연산자의 갯수를 복구한다.
                operator[i]++;
            }
        }
    }
}

​