[Java] BOJ 14888 연산자 끼워넣기

 

14888번: 연산자 끼워넣기

---

정답 코드

• 완전 탐색 + 사칙연산 구현 문제
• 입력으로 받은 연산자 만큼 재귀함수 탐색

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, min, max, sum;
    static int[] num;
    static Queue<Integer> queue;

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

        N = Integer.parseInt(br.readLine());

        num = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(st.nextToken());
        }

        int[] oper = new int[4];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < oper.length; i++) {
            oper[i] = Integer.parseInt(st.nextToken());
            sum += oper[i];
        }

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

        fun(oper, new LinkedList<>(), 0);

        System.out.println(max);
        System.out.println(min);
    }

    private static void fun(int[] oper, Deque<Integer> deque, int detph) {
        if (detph == sum) {
            int calc = calc(toString(deque));
            max = Math.max(max, calc);
            min = Math.min(min, calc);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (oper[i] > 0) {
                oper[i]--;
                deque.addLast(i);
                fun(oper, deque, detph + 1);
                oper[i]++;
                deque.removeLast();
            }
        }
    }

    private static String toString(Deque<Integer> deque) {
        StringBuilder sb = new StringBuilder();
        int size = deque.size();
        for (int i = 0; i < size; i++) {
            int n = deque.pollFirst();
            sb.append(Integer.toString(n));
            deque.addLast(n);
        }
        return sb.toString();
    }

    private static int calc(String str) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < num.length; i++) {
            queue.add(num[i]);
        }

        int value = queue.poll();
        int index = 0;
        while (!queue.isEmpty()) {
            char c = str.charAt(index++);
            int n = queue.poll();
            if (c == '0') {
                value += n;
            } else if (c == '1') {
                value -= n;
            } else if (c == '2') {
                value *= n;
            } else {
                value /= n;
            }
        }

        return value;
    }
}