백준 1700번 - 멀티탭 스케줄링

문제

백준 1700번 - 멀티탭 스케줄링

아이디어

• 멀티탭에 플러그를 하나씩 꽂으면서 더 이상 멀티탭 구멍이 남지 않은 상태에서 새로운 플러그를 꽂아야 할 때는 곧 다시 사용할 플러그는 남기고, 최대한 나중에 다시 쓰이는 플러그를 제거하는 것이 유리하다.
• 코드랑 주석 설명 참고

예상 시간 복잡도

• 멀티탭 구멍 개수 : N
• 전기용품 사용 횟수 : K
• 예상 시간 복잡도 : O(K^2 x N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class BJ_1700 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] used = new int[k];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            used[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0; //플러그를 빼는 횟수

        HashSet<Integer> multiTap = new HashSet<>(); //멀티탭

        for (int i = 0; i < k; i++) {

            //멀티탭에 꽂혀 있지 않고, 멀티탭이 가득 찬 경우
            //멀티탭에 꽂혀있는 플러그 중 하나를 빼야 한다.
            if (!multiTap.contains(used[i]) && multiTap.size() >= n) {

                //멀티탭에 꽂혀있는 플러그 중 나중에 또 써야 할 플러그 목록(순서 중요)
                ArrayList<Integer> reuse = new ArrayList<>();

                //멀티탭에 꽂혀있는 플러그 중 나중에 쓰이지 않을 플러그 목록
                HashSet<Integer> remain = new HashSet<>(multiTap);

                //나중에 써야 할 전기 용품 목록 탐색
                for (int j = i; j < k; j++) {

                    //나중에 써야 할 플러그가 이미 멀티탭에 꽂혀 있다
                    if (multiTap.contains(used[j]) && !reuse.contains(used[j])) {

                        //나중에 또 써야 할 플러그 목록에 추가
                        reuse.add(used[j]);

                        //나중에 쓰이지 않을 플러그 목록만 남기기 위해 제거
                        remain.remove(used[j]);
                    }
                }

                //만약 나중에 또 써야 할 플러그 수가 멀티탭 구멍보다 많다면 가장 마지막에 쓰일 플러그를 제거한다.
                if (reuse.size() >= n) {
                    multiTap.remove(reuse.get(reuse.size() - 1));

                //그렇지 않다면 나중에 쓰이지 않을 플러그들 중 아무거나 빼도 상관없다.
                } else if (!remain.isEmpty()) {
                    multiTap.remove(remain.iterator().next());
                }

                count++;
            }

            multiTap.add(used[i]); //멀티탭에 플러그 꽂기
        }

        System.out.println(count);
    }
}