SWEA 4008번 [모의 SW 역량테스트] 숫자 만들기 (JAVA

SWEA 4008번 [모의 SW 역량테스트] 숫자 만들기 (JAVA)

문제

풀이

각 연산자의 개수 만큼 빈 공간을 선택, 선택된 빈 공간에 연산자 대입

다음 연산자에서 앞 선 작업을 반복

동일한 연산자가 들어갈 위치를 선택하면 순서는 상관 없다.

이미 연산자가 위치한 경우 다음 연산자는 들어갈 수 없다.

코드

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

public class Solution {

    static char[] operator = { '+', '-', '*', '/' };
    static int[] count = { 0, 0, 0, 0 };
    static int[] numbers;

    static char[] selected;
    static boolean[] visited;

    static int N, min, max;

    public static void main(String[] args) throws Exception {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(in.readLine());

        for (int t = 1; t <= T; t++) {
            sb.append("#").append(t).append(" ");

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

            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                count[i] = Integer.parseInt(st.nextToken());
            }

            numbers = new int[N];
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < N; i++) {
                numbers[i] = Integer.parseInt(st.nextToken());
            }

            selected = new char[N - 1];
            visited = new boolean[N - 1];
            min = Integer.MAX_VALUE;
            max = Integer.MIN_VALUE;

            comb(0, 0, 0);

            int answer = Math.abs(max - min);
            sb.append(answer).append("\n");
        }

        out.write(sb.toString());
        out.close();
    }

    private static void comb(int start, int depth, int cnt) {
        if (depth == count[cnt]) {
            if (cnt == 3) {
                int temp = numbers[0];
                for (int i = 0; i < N - 1; i++) {
                    char oper = selected[i];
                    int next = numbers[i + 1];

                    if (oper == '+') {
                        temp += next;
                    } else if (oper == '-') {
                        temp -= next;
                    } else if (oper == '*') {
                        temp *= next;
                    } else if (oper == '/') {
                        temp /= next;
                    }
                }

                min = Math.min(min, temp);
                max = Math.max(max, temp);

                return;
            }
            comb(0, 0, cnt + 1);
        }

        for (int i = start; i < N - 1; i++) {
            if (!visited[i]) {
                visited[i] = true;
                selected[i] = operator[cnt];
                comb(i + 1, depth + 1, cnt);
                visited[i] = false;
            }
        }
    }

}