220817 - 멀티탭 스케줄링

◾ 멀티탭 스케줄링 : 백준 1700번 (골드 1)

• https://www.acmicpc.net/problem/1700

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

---

입력

• 첫째 줄 : 멀티탭 구멍의 개수 N( 1 <= N <= 100), 전기 용품 사용횟수 K (1 <= K <= 100)
• 둘째 줄 : 전기 용품의 이름 사용 순서대로 입력.

출력

• 플러그를 빼는 최소 횟수.

입출력 예

Input	Output
2 7 2 3 2 3 1 2 7	2

---

◾ 풀이

1. 해설

• 탐욕 알고리즘 기법 : 콘센트를 사용중인 기기 중 다음 사용까지 가장 길게 남은 기기 제거 후 새로운 기기 추가.
  1. 콘센트 확인.
  2. 콘센트에 빈 자리가 있다면.
     • 새로운 기기 추가.
  3. 콘센트에 빈 자리가 없다면.
     • 사용중인 기기 중 다음 사용까지 가장 길게 남은 기기 제거.
     • 해당 자리에 새로운 기기 추가.
  4. 위의 동작 반복.

---

2. 프로그램

• n : 플러그의 수
• k : 기기 사용 횟수
• useOrder : 사용 순서. (int[])
• product : 기기별 사용 순서. (key : 기기 번호, value : 사용 순서 큐)
• use : 기기별 콘센트 사용 여부. (boolean[])
• heap : 콘센트 상태 힙. (기기의 다음 사용 순서 기준 내림차순 정렬)
• answer : 플러그를 뺀 최소 횟수.

1. n, k, useOrder , product 입력
2. use, heap, answer 초기화.
3. useOrder에 따라 콘센트 사용.
   • 이미 콘센트를 사용중인 경우(use[key]) : 비교를 다시 하기 위해 힙에서 제거 후 재추가.
     • heap.remove(key) : 비교를 위해 힙에서 삭제.
   • 콘센트를 모두 사용중인 경우(heap.size() == n) : 다음 순서가 가장 늦은 기기 제거 후 새로운 기기 추가.
     • use[heap.poll()] = false : 기존 기기 제거 및 콘센트 사용 여부 false 변경.
     • answer += 1 : 플러그 뺀 횟수 증가.
   • 공통 동작.
     • product.get(key).pollFirst() : 기기의 사용 순서 제거.
     • use[key] = true : 기기의 콘센트 사용 표시.
     • heap.offer(key) : 새로운 기기 추가.

# 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

		st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken()); // 플러그의 수
		int k = Integer.parseInt(st.nextToken()); // 사용 순서

		// 사용 순서 입력.
		int[] useOrder = Arrays.stream(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

		// 각 전자 기기별 사용 순서 저장.
		// key(Integer) : 전자 기기 번호.
		// value(Deque<Integer>) : 사용 순서 큐.
		Map<Integer, Deque<Integer>> product = new HashMap<>();
		for (int i = 0; i < k; i++) {
			// 해당 키가 없다면 생성.
			if (!product.containsKey(useOrder[i])) {
				product.put(useOrder[i], new LinkedList<>());
			}
			// 사용 순서 추가.
			product.get(useOrder[i]).offerLast(i);
		}

		// 전자 기기에 대해 마지막 순서로 1000 추가.
		// 1000은 더이상 사용하지 않음을 의미.
		for (int i = 1; i <= k; i++) {
			if (product.containsKey(i)) {
				product.get(i).offerLast(1000);
			}
		}

		// 플러그 뺀 횟수
		int answer = 0;
		// 기기별 콘센트 사용 여부.
		boolean[] use = new boolean[k + 1];
		// 콘센트 상태를 담을 힙.
		// - 전자 기기의 다음 순서 기준 내림 차순 정렬.
		// - 다음 순서가 길게 남은 것 부터 콘센트에서 제거.
		PriorityQueue<Integer> heap = new PriorityQueue<>((key1, key2) -> {
			int res = product.get(key1).peekFirst() - product.get(key2).peekFirst();
			return -res;
		}

		);

		// 모든 사용 순서 진행.
		for (int i = 0; i < k; i++) {
			// 현재 콘센트에서 사용할 기기 변수.
			int key = useOrder[i];

			// 사용중인 기기라면
			// 값 업데이트를 위해 힙에서 제거.
			if (use[key]) {
				heap.remove(key);
			// 사용중이지 않은 기기이며 콘센트가 가득 찬 경우
			// 힙의 루트 제거. 사용 상태 변경. 플러그 빼는 횟수 증가.
			} else if (heap.size() == n) {
				use[heap.poll()] = false;
				answer += 1;
			}
			// product의 value 크기가 1인 경우 : deque<Integer>에 '1000'만 남은 경우
			// 따라서, 1보다 큰 경우에만 값 제거.
			if (product.get(key).size() != 1)
				product.get(key).pollFirst();
			// 콘센트 사용 표시.
			use[key] = true;
			heap.offer(key);
		}

		sb.append(answer);
		System.out.println(sb);
	}
}