1700번 - 멀티탭스케줄링(나중에 사용되는 요소)

최근 푼 문제중 가장 티어가 높은 문제로 골드 2티어의 문제이다.

사용할 제품과 돼지코의 수가 주어지고, 제품의 사용순서가 주어지며, 제품은 중복 사용이 된다.

이 때 코드를 가장 적게 뽑는 횟수를 구하는 것이다.

처음에는 재귀를 이용했다. 때문에 너무 많이 불필요한 검사를 했고, 시간 초과가 되었다.

아래는 해당 코드이다.

import java.util.Scanner;

public class 멀티탭스케줄링_1700번_시간초과 {
    static int N, K;
    static int[] products;
    static boolean[] stuck;
    static int min = 100;
    static int[] consent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        products = new int[K];
        stuck = new boolean[K+1];
        consent = new int[N];

        for (int i = 0; i < K; i++) {
            products[i] = sc.nextInt();
        }
        unplug(0,0,0);

        System.out.println(min);
    }

    static void unplug(int start, int count, int sum) {
        if (sum >= min) {
            return;
        }
        for (int i = start; i < K; i++) {
            int num = products[i];
            if (stuck[num]) {
                start++;
                continue;
            }
            if (count == N) {
                for (int j = 0; j < N; j++) {
                    int temp = consent[j];
                    consent[j] = products[i];
                    stuck[products[i]] = true;
                    stuck[temp] = false;
                    unplug(start+1, count, sum+1);
                    consent[j] = temp;
                    stuck[products[i]] = false;
                    stuck[temp] = true;
                }
                return;
            } else {
                consent[count++] = num;
                stuck[products[i]] = true;
                start++;
            }
        }
        min = sum;
    }


}

비록 지금 돼지코에 어떤 제품이 꽂혀있는지는 고려했지만, 나중에 사용할 제품을 고려하지 않았다.

지금 돼지코에 꽂혀 있는 제품 중 나중에 사용될 제품을 고려하면, 한과정 한과정 많은 시간이 소요되는 것 같아도,

결국 한 과정만 하면 되기에, 재귀보다 훨씬 빠른 속도로 문제를 풀게된다.

아래서는 나중에 사용될 제품을 리스트에 넣고 가장 늦게 사용되는 제품을 빼는 풀이법이다.

import java.util.*;

public class 멀티탭스케줄링_1700번 {
    static int N, K;
    static int[] products;
    static boolean[] stuck;
    static int sum = 0;
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        products = new int[K];
        stuck = new boolean[K+1];

        for (int i = 0; i < K; i++) {
            products[i] = sc.nextInt();
        }

        unplug();

        System.out.println(sum);
    }

    static void unplug() {
        for (int i = 0; i < K; i++) {
            int num = products[i];
            if (!stuck[num]) {
                if (count < N) { // 일단 다 찰때까지 꽂기
                    count++;
                    stuck[num] = true;
                } else { // 다 찼으면
                    ArrayList<Integer> list = new ArrayList<>();
                    for (int j = i; j < K; j++) {
                        int temp = products[j];
                        if (stuck[temp] && !list.contains(temp)) { //  꽂혀있는 콘센트 중 나중에 사용되지 않는 콘센트 찾기
                            list.add(temp);
                        }
                    }
                    if (list.size() < N) { // 꽂혀있는 콘센트 중 나중에 사용되지 않는 콘센트가 있는 경우
                        for (int j = 0; j < N+1; j++) {
                            if (stuck[j] && !list.contains(j)) {
                                stuck[j] = false;
                                break;
                            }
                        }
                    } else { // 꽂혀있는 모든 콘센트가 사용되는 경우 가장 나중에 사용될 콘센트를 제거
                        stuck[list.get(list.size()-1)] = false;
                    }
                    stuck[num] = true; // 하나 제거가 되었으니 하나 추가
                    sum++; // 뽑은 횟수 1회 추가
                }
            }
        }
    }
}

재귀문제를 몇문제 풀다보니, 너무 사고가 재귀쪽으로 치우친 것같다.
재귀는 상당히 시간이 오래 걸리는 방법이니, 일단 문제 해결법을 찾은 후 정말 재귀를 사용해야 한다면 그 때 사용하도록 하자.