[백준 Gold 1] 1700 멀티탭 스케줄링 - Java

문제링크 : https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

접근 과정 : 

• 문제를 보자마자, 페이지 교체 알고리즘 중 최적 페이지 교체 알고리즘이 생각났다.
• 실제로는, 미래에 어떤 페이지를 가장 사용하지 않을지 모르기에 사용할 수 없는 알고리즘.
• 그러나 문제에는 어떤 전기용품들이 사용될 지 알려주고 있다.!!!!
• 현재 사용중인 전기용품들중, 가장 오랫동안 사용되지 않을 전기용품을 교체한다!!

 

소스 코드 및 결과 :

package BOJ;

/* 
    멀티탭 스케줄링
*/

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

public class BOJ1700 {

    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[] tool = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            tool[i] = Integer.parseInt(st.nextToken());
        }
        br.close();

        int change = 0;

        if (N == 1) {
            for(int i = 1; i<K; i++){
                if (tool[i] != tool[i-1]) {
                    change++;
                }
            }

        } else {
            HashSet<Integer> multitap = new HashSet<>();

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

                if (multitap.contains(tool[i])) {
                    continue;
                }

                if (multitap.size() < N) {
                    multitap.add(tool[i]);
                } else {
                    HashSet<Integer> temp = new HashSet<>(multitap);
                    for (int j = i + 1; j < K; j++) {
                        if (temp.contains(tool[j])) {
                            temp.remove(tool[j]);
                        }
                        if (temp.size() < 2) {
                            break;
                        }
                    }

                    multitap.remove(temp.iterator().next());
                    multitap.add(tool[i]);
                    change++;
                }
            }
        }

        System.out.println(change);

    }
}

 

P.S 

앞으로 가장 사용되지 않을 전기용품을 고르기 위해, MultiTap HashSet을 새로운 Temp HashSet으로 복사한다..

문제에서는 멀티탭의 크기가 어마어마하게 크지 않아서 괜찮았다.

다만, 이러한 부분을 고려해서 더 좋은 방법을 찾으면 더 좋지 않을까..