[BOJ] 백준 1700 멀티탭 스케줄링

Set 사용: 기기의 종류가 적어서 속도 측면에서는 좀 느림! (but, 메모리 효율적)

 

[문제]

https://www.acmicpc.net/problem/1700

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
    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());
    	st = new StringTokenizer(br.readLine());
    	int[] order = new int[k];
    	for(int i=0;i<k;i++) {
    		order[i] = Integer.parseInt(st.nextToken());
    	}
    	int result = 0;
    	HashSet<Integer> hs = new HashSet<>();
    	for(int i=0;i<k;i++) {
    		if(hs.contains(order[i])) continue;
    		if(hs.size()<n) {
    			hs.add(order[i]);
    		}
    		else {
    			List<int[]> list = new ArrayList<>();
    			for(int v : hs) {
    				boolean use = false;
    				for(int j=i+1;j<k;j++) {
        				if(v==order[j]) {
        					list.add(new int[] {j,v});
        					use = true;
        					break;
        				}
        			}
    				if(!use) {
    					list.add(new int[] {k,v});
    				}
    			}
    			list.sort((a,b)->{
    				return b[0] - a[0];
    			});
    			int pick = list.get(0)[1];
    			hs.remove(pick);
    			result++;
    			hs.add(order[i]);
    		}
    	}
    	System.out.println(result);
    }
}