[1700번] 멀티탭 스케줄링 ( set 자료구조, List )

---

---

✅ 증명

현재 꽂아져 있는 플러그가 (2,3)이고 현재 1번 기기를 사용하기 위해 플러그를 하나 빼야한다고 하자. 2번 기기는 5차례 이후에 다시 사용하고 3번 기기는 10차례 이후 다시 사용한다고 하면, 2번 기기를 선택할 경우 5차례 이후에 다시 플러그를 빼야 하는 경우가 발생하고 3번 기기를 선택할 경우 10차례 이후에 다시 플러그를 빼야하는 경우가 발생하게 된다.

따라서, 3번기기를 뽑는 것이 2번기기를 뽑는 것 보다 더 긴 시간동안 플러그를 바꿀 확률이 더 같거나 낮아지게 되므로 해당 방식이 그리디한 선택임을 알 수 있으므로 '현재 꽂아져 있는 기기들 중 가장 나중에 사용되는 기기 플러그를 빼는 최적해가 존재한다'는 참임을 알 수 있다.

---

✅ List와 set

주로 쓰던 ArrayList를 쓰면 subList과정에서 타입 캐스팅이 필요하다.
따라서, 코드의 유연성을 위해 일반적으로는 List A = new ArrayList<>();와 같이 상위 인터페이스 타입을 사용하는 것이 좋다고 한다.

List<Integer> subA = A.subList(i + 1, term);

---

✅ 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());

		int size = Integer.parseInt(st.nextToken());
		int term = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		List<Integer> A = new ArrayList<>();
		for (int i = 0; i < term; i++) {
			A.add(Integer.parseInt(st.nextToken()));
		}

		Set<Integer> set = new HashSet<>();
		int num = 0;
		int[] seq = new int[size];
		int cnt = 0;

		for (int i = 0; i < term; i++) {
			num = A.get(i);
			if (set.contains(num)) continue;
			if (set.size() < size) {
				set.add(num);
				continue;
			}
			int max = -1, idx = -1;
			for (int s : set) {
				List<Integer> subA = A.subList(i + 1, term);

				int temp;
				if (subA.contains(s)) {
					temp = subA.indexOf(s) + 1;
				} else {
					temp = term - i - 1;
				}
				if (temp > max) {
					max = temp;
					idx = s;
				}
			}

			set.remove(idx);
			set.add(num);
			cnt++;

		}

		System.out.println(cnt);


	}
}

---