[BOJ 1700] 멀티탭 스케줄링

문제

• BOJ 1700
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

상황을 다음과 같이 나눠서 접근할 수 있다.
1.전자기기를 순서대로 꽂는데 이때 이미 꽂힌 전자기기이면 continue.
2.아직 안꽂혔다면 꽂을 위치를 찾는다.
2-1.멀티탭에 빈자리가 있는 경우 continue.
2-2.빈자리가 없는 경우 멀티탭에서 사용중인 전자기기 중 가장 나중에 사용될 전자기기를 찾아서 뽑는다.
: 가장 나중에 사용될 전자기기를 찾을 때 멀티탭에 꽂혀져 있는 전자기기가 다음 electrics[i+1]부터 언제 가장 마지막에 사용되는지를 구한다.
2-3.구했다면 해당 idx위치의 멀티탭을 뽑고 새로운 전자기기 electrics[j]를 꽂아준다.

2-2번을 어떻게 구현할지를 해결하는것이 포인트였던것 같다.. 처음엔 무조건 개수를 세서 적게 나오는 전자기기를 뽑고 거기에 꽂아주면 된다고 생각했는데,
꽂는 개수는 적지만 바로 다음 순서라면 해당 자리를 뺄 필요가 없기 때문에 올바르지 않다.
따라서, 가장 나중에 사용되는 전자기기를 찾아 뽑아야 원하는 답을 얻을 수 있다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, K;
	static int[] electrics, multitabs; // 사용 순서대로 전자기기 번호, 멀티탭
	static boolean[] used; // 사용중인 전자기기
	static int Ans;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		electrics = new int[K + 1];
		multitabs = new int[N + 1];
		used = new boolean[K + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= K; i++) {
			electrics[i] = Integer.parseInt(st.nextToken());
		} // End input

		// 전자기기를 순서대로 멀티탭에 꽂는다.
		for (int i = 1; i <= K; i++) {
			// 멀티탭에 이미 꽂아있으면 다음 탐색
			if (used[electrics[i]]) {
				continue;
			} else {// 아직 안꽂아 있으면
				// 멀티탭에 빈자리가 있는지 탐색
				boolean find = false;
				for (int j = 1; j <= N; j++) {
					if (multitabs[j] == 0) {
						find = true;
						multitabs[j] = electrics[i];
						used[electrics[i]] = true;
						break;
					}
				}

				// 멀티탭에 빈자리 있는 경우
				if (find) {
					used[electrics[i]] = true;
					continue;
				} else { // 빈자리 없는 경우
					// 마지막 전자기기인경우 아무거나 빼고 종료
					if (i == K) {
						Ans++;
						break;
					}

					int idx = 0, maxIdx = -1;

					// 멀티탭에 꽂혀져있는 전자기기중 더이상 사용가능성 낮은 전자기기를 뺀다.
					for (int j = 1; j <= N; j++) {
						int lastIdx = 0;

						for (int k = i + 1; k <= K; k++) {
							if (electrics[k] == multitabs[j])
								break;
							lastIdx++;
						}

						if (lastIdx > maxIdx) { //더 멀리 사용되는 전자기기를 선택한다.
							idx = j;
							maxIdx = lastIdx;
						}
					}

					Ans++;
					used[multitabs[idx]] = false;
					multitabs[idx] = electrics[i];
					used[electrics[i]] = true;
				}
			}
		}

		System.out.println(Ans);
	}
}