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

문제

 

 

접근 방식

플러그를 최소한으로 빼면서 전기용품을 사용하려면

이후에 다시 쓰일 전기용품의 플러그를 빼는 것보단

나중에 쓰일 일이 없는 플러그를 빼는 것이 효율적일 것이고

만약 나중에 쓰인다면 가장 나중에 쓰이는 것을 빼는 게 효율적이다.

 

아래와 같이 상황을 세 가지로 나누어 처리해 주면 된다.

1. 이미 멀티탭에 꽂힌 전기용품이면 그대로 사용하면 되니 아무런 행동도 하지 않음
2. 멀티탭에 빈 공간이 있는 경우에는 그대로 빈 공간에 꽂음
3. 빈 공간이 없으면 앞으로 사용되지 않거나 가장 나중에 사용되는 것을 빼고 새로 꽂음

 

첫 번째 상황을 처리하기 위해 불리언 배열을 만들어

멀티탭에 꽂거나 뺄 때마다 상태를 바꿔주었고

 

두 번째와 세 번째 상황을 처리하기 위해 정수형 배열을 만들어

멀티탭에 꽂혀 있는 플러그들이 어떤 것인지 알 수 있게 저장했다.

 

풀이

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[] history = new int[k + 1];

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i <= k; i++) {
			history[i] = Integer.parseInt(st.nextToken());
		}

		int tab = n;
		int[] arr = new int[n];
		boolean[] isUsed = new boolean[k + 1];
		int count = 0;

		for (int i = 1; i <= k; i++) {
			int target = history[i];
			int idx = 0;
			int late = 0;

			if (isUsed[target]) continue;
			if (tab > 0) {
				tab--;
				for (int j = 0; j < n; j++) {
					if (arr[j] == 0) {
						arr[j] = target;
						break;
					}
				}
				isUsed[target] = true;
				continue;
			}

			count++;

			for (int j = 0; j < n; j++) {
				int use = arr[j];
				int x = 0;

				for (int l = i + 1; l <= k; l++) {
					if (history[l] == use) {
						x = l;
						break;
					}
				}

				if (x == 0) {
					idx = j;
					break;
				}

				if (x > late) {
					late = x;
					idx = j;
				}
			}

			tab--;
			isUsed[arr[idx]] = false;
			isUsed[target] = true;
			arr[idx] = target;
		}

		System.out.println(count);
	}
}