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

1. 문제 유형 : 그리디

2. 시간복잡도 : O(K*(K^2+N)

 

멀티탭에서 코드를 최소로 뽑는 횟수를 구하는 문제이다.

1. 멀티탭에 이미 꽂혀있으면 넘어감

2. 멀티탭에 꽂혀있지는 않지만, 비어있는 곳이 있다면 꽂고 넘어감

3. 멀티탭에 새로 꽂아야 하지만, 멀티탭 공간이 없는 경우

 

3번이 문제의 핵심인데, 앞으로 꽂아야하는 전자기기 중 가장 나중에 나오는 전자기기를 멀티탭에서 제거하면 된다. 즉, 현재 전자기기를 꽂을 거지만, 다음에 혹은 다다음에 또 나오는 전자기기라면 다시 사용해야 하기 때문에, 가장 나중에 나올법 한 전자기기를 파악하여 그 전자기기를 멀티탭에서 제거하면 된다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] list = new int[K];
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < K; i++) {
			list[i] = Integer.parseInt(st.nextToken());
		}
		
		int answer = 0;
		int[] selected = new int[N];
		int idx = 0;
		while(idx < K) {
			boolean[] temp = new boolean[N];
			int i;
			for (i = 0; i < N; i++) {
				// 이미 꽂혀있다면 넘어감
				if(selected[i] == list[idx]) {
					idx++; 
					break;
				}
				if(selected[i] == 0) {
					// 안꽂힌 곳이 있다면 꽂는다
					selected[i] = list[idx];
					idx++;
					break;
				}
			}
			if(i == N) {
				// 다 꽂혀있다면 하나를 빼고 꽂아야 한다
				// 이후에 무슨 전자기기를 꽂을지 파악한다.
				int tCnt = 0; // temp에 N-1개가 true로 되었는지 확인할 변수
				int nextIdx = idx+1;
				while(tCnt != N-1 && nextIdx < K) {
					for (int j = 0; j < N; j++) {
						if(temp[j]) continue;
						if(selected[j] == list[nextIdx]) {
							// 이미 꽂혀잇다면
							temp[j] = true;
							tCnt++;
							break;
						}
					}
					nextIdx++;
				}
				
				for (int j = 0; j < N; j++) {
					// temp가 false인 부분을 교체
					if(!temp[j]) {
						selected[j] = list[idx];
						answer++;
						break;
					}
				}
				idx++;
				
			}
		}
		System.out.println(answer);
	}

}