[Java] BOJ1700_멀티탭 스케줄링

www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

---

꽂혀있는 플러그 중 처음으로 사용되는 시점이 가장 나중인 것을 교체하는 방법으로 그리디 접근을 하였다.

 

count 배열은 각 장치별 남은 사용 횟수를 담고 있다.

 

콘센트를 탐색하여 이미 장치의 플러그가 꽂혀있는지와 빈자리가 있는지 판단한다. 현재 꽂으려는 장치(cur)가 이미 꽂혀있다면 패스하였고 꽂혀있지 않고 콘센트에 빈자리가 있다면 해당 콘센트에 장치를 꽂아준다.

 

모든 콘센트에 플러그가 꽂혀있고 현재 장치가 이미 꽂혀있지 않은 상태라면 먼저 현재 꽂혀있는 장치 중 앞으로 사용하게 될 경우가 없는, 즉 count가 0인 장치를 뽑아 교체해준다.

 

count가 0인 장치가 없다면 처음으로 사용되는 시점이 가장 나중인 장치를 뽑아야 한다. 방문 처리 배열을 만들어주고 가장 마지막에 방문처리 배열을 채우는 장치를 뽑아주면 된다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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());
		int[] count = new int[K+1];
		int[] arr = new int[K];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < K; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			count[arr[i]]++;
		}
		int[] multi = new int[N];
		int res = 0;
		for (int i = 0; i < K; i++) {
			int cur = arr[i];
			count[cur]--;
			boolean flag = false;
			for (int j = 0; j < N; j++) {
				if(multi[j] == cur) {
					flag = true;
					break;
				} else if(multi[j]==0) {
					multi[j] = cur;
					flag = true;
					break;
				}
			}
			if(!flag) {
				int find = -1;
				for (int j = 0; j < N; j++) {
					if(count[multi[j]] == 0) {
						find = j;
						break;
					}
				}
				if(find != -1) {
					multi[find] = cur;
				} else {
					//처음으로 사용되는 시점이 가장 나중인 장치
					boolean[] visit = new boolean[N];
					int cnt = 0;
					for (int j = i+1; j < K; j++) {
						boolean f = false;
						for (int c = 0; c < N; c++) {
							if(arr[j] == multi[c] && !visit[c]) {
								visit[c] = true;
								cnt++;
								if(cnt == N) {
									find = c;
									f = true;
									break;
								}
							}
						}
						if(f) break;
					}
					multi[find] = cur;
				}
				
				res++;
			}
		}
		System.out.println(res);
	}

}