[SWEA] 4008. 숫자만들기

처음에 연산자카드를 고를 때마다 연산을 해주었더니 연산량이 너무 많아져서 시간이 5002ms가 걸렸다.. 연산자 카드를 모두 고르고 연산을 해주었더니 129ms로 줄어서 통과되었다. 그리고 카드의 개수 배열을 visited처럼 사용했더니 코드가 더 간결해졌다.

시간초과가 난 코드(5002ms)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    static char[] op;
    static int[] num;
    static boolean[] visited;
    static int N;
    static int res1 = Integer.MAX_VALUE;
    static int res2 = Integer.MIN_VALUE;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= T; tc++) {
            res1 = Integer.MAX_VALUE;
            res2 = Integer.MIN_VALUE;
            N = Integer.parseInt(in.readLine());

            int[] input = new int[4];
            op = new char[N - 1];
            visited = new boolean[N - 1];
            num = new int[N];

            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                input[i] = Integer.parseInt(st.nextToken());
            }
            int index = 0;
            // +
            for (int i = 0; i < input[0]; i++) {
                op[index++] = '+';
            }
            // -
            for (int i = 0; i < input[1]; i++) {
                op[index++] = '-';
            }
            // *
            for (int i = 0; i < input[2]; i++) {
                op[index++] = '*';
            }
            for (int i = 0; i < input[3]; i++) {
                op[index++] = '/';
            }

            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }
            char[] output = new char[N - 1];
            int sum = num[0];
            perm(0, output, sum);
            sb.append("#" + tc + " " + (res2 - res1) + "\n");

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

    private static void perm(int cnt, char[] output, int sum) {
        if (cnt == N - 1) {
            // System.out.println(Arrays.toString(output));
            // System.out.println(sum);
            res1 = Math.min(res1, sum);
            res2 = Math.max(res2, sum);
            return;
        }

        for (int i = 0; i < N - 1; i++) {
            if (visited[i] != false)
                continue;
            visited[i] = true;
            output[cnt] = op[i];
            int temp = sum;
            if (op[i] == '+') {
                temp += num[cnt + 1];
            } else if (op[i] == '-') {
                temp -= num[cnt + 1];
            } else if (op[i] == '*') {
                temp *= num[cnt + 1];
            } else {
                temp /= num[cnt + 1];
            }

            perm(cnt + 1, output, temp);
            visited[i] = false;

        }
    }

}

정답코드(129ms)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int[] num, isSelected;
    static int N;
    static int[] card = new int[4];
    static int min_res;
    static int max_res;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= T; tc++) {
            min_res = Integer.MAX_VALUE;
            max_res = Integer.MIN_VALUE;
            N = Integer.parseInt(in.readLine());
 
            isSelected = new int[N];
            num = new int[N];
 
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < 4; i++) {
                card[i] = Integer.parseInt(st.nextToken());
            }
 
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }
 
            perm(0);
            sb.append("#" + tc + " " + (max_res - min_res) + "\n");
 
        }
        out.write(sb.toString());
        out.flush();
        out.close();
    }
 
    private static void perm(int cnt) {
 
        if (cnt == N - 1) {
            int cal = num[0];
            for (int i = 1; i < N; i++) {
                if (isSelected[i - 1] == 0) {// +일 때
                    cal += num[i];
                } else if (isSelected[i - 1] == 1) { // - 일 때
                    cal -= num[i];
                } else if (isSelected[i - 1] == 2) { // * 일 때
                    cal *= num[i];
                } else { // /일 때
                    cal /= num[i];
                }
            }
            min_res = Integer.min(min_res, cal);
            max_res = Integer.max(max_res, cal);
            return;
 
        }
 
        for (int i = 0; i < 4; i++) {
            if (card[i] == 0)
                continue;
            card[i]--;
            isSelected[cnt] = i;
            perm(cnt + 1);
            card[i]++;
        }
 
    }
 
}