====== 멀티탭 스케줄링 ======

===== 풀이 =====
  * 이 문제는 운영체제 분야에서 중요하게 다뤄지는 Page Replacement 문제를 멀티탭에 비유해서 옮겨놓은 문제이다.
  * 이렇게 모든 디바이스의 사용 타이밍이 offline으로 전부 주어져있는 경우에는 [[ps:그리디#Page Replacement|Belady's algorithm]] 을 따르는 것이 최적이다. 이것은 다음에 사용될 시간이 가장 멀리 떨어져있는 디바이스를 우선적으로 뽑는 그리디 알고리즘이다.
  * 이 알고리즘을 최적화된 방식으로 구현하려면, 먼저 각 디바이스마다 사용되는 시간들을 리스트에 저장해놓고, 현재 꼽혀있는 기기들과 그 기기들의 다음 사용 시간을 우선순위 큐로 관리하면 새 기기를 꼽아야 할때마다 뽑을 기기를 O(logN)에 계산 가능하므로 총 O(MlogN)에 풀수 있다.
  * 다만 그렇게 구현할 경우, 현재 꼽혀있는 기기를 다시 사용하는 경우를 처리하는 것을 비롯해서 구현이 번거로운 부분들이 있다. 제한이 워낙 작아서 그냥 우선순위큐를 쓰지 않고, 꼽혀있는 기기들에 대해서 다음 사용시간을 일일히 비교하는 식으로 O(MN)에 구현해도 충분히 빠르다.
  * 굳이 우선순위큐를 쓴다면 teflib.priorityqueue.PriorityDict를 쓰면 그나마 좀 쉽게 구현가능하긴 한데, 워낙 제한이 작다보니 시간은 더 오래걸렸다 

===== 코드 =====

==== 코드 1 - O(MN) ====
<dkpr py>
"""Solution code for "BOJ 1700. 멀티탭 스케줄링".

- Problem link: https://www.acmicpc.net/problem/1700
- Solution link: http://www.teferi.net/ps/problems/boj/1700

Tags: [Greedy]
"""

INF = float('inf')


def main():
    N, K = [int(x) for x in input().split()]
    devices = [int(x) - 1 for x in input().split()]

    times_by_device = [[INF] for _ in range(K)]
    for time, device in reversed(list(enumerate(devices))):
        times_by_device[device].append(time)

    plugged = set()
    answer = 0
    for device in devices:
        times_by_device[device].pop()
        if device not in plugged and len(plugged) == N:
            device_to_unplug = max(
                plugged, key=lambda device: times_by_device[device][-1])
            plugged.remove(device_to_unplug)
            answer += 1
        plugged.add(device)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

==== 코드 2 - O(MlogN) ====

<dkpr py>
"""Solution code for "BOJ 1700. 멀티탭 스케줄링".

- Problem link: https://www.acmicpc.net/problem/1700
- Solution link: http://www.teferi.net/ps/problems/boj/1700

Tags: [Greedy]
"""

from teflib import priorityqueue

INF = float('inf')


def main():
    N, K = [int(x) for x in input().split()]
    devices = [int(x) - 1 for x in input().split()]

    times_by_device = [[INF] for _ in range(K)]
    for time, device in zip(range(K, 0, -1), reversed(devices)):
        times_by_device[device].append(time)

    plugged_devices = priorityqueue.PriorityDict()
    answer = 0
    for device in devices:
        if device not in plugged_devices and len(plugged_devices) == N:
            plugged_devices.pop_min()
            answer += 1
        times_by_device[device].pop()
        plugged_devices[device] = -times_by_device[device][-1]

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>


{{tag>BOJ ps:problems:boj:골드_3}}