[백준] 1700 멀티탭 스케줄링, python

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

 

각 전기용품이 사용되는 순서 인덱스를 저장한다.

순서가 2, 3, 2, 3, 1, 2, 7이면

1은 4에, 2는 0,2,5에, 3은 1,3에 7은 6에 등장하므로 해당 인덱스들을 저장한다

플러그 딕셔너리를 생성한다. key=전기용품종류, value=사용되는 순서(배열의 인덱스)로 저장된다.

플러그가 비어있다면 전기용품을 꽂고 딕셔너리에 추가하고, 사용 중인 전기용품이면 딕셔너리 인덱스를 늘린다.

딕셔너리에 없는 전기용품을 사용할때 현재 사용순서로부터 사용순서가 제일 멀리 떨어진 전기용품을 뽑는다.

전기용품	사용되는 순서	플러그 딕셔너리	설명
2	0	{2:0}	딕셔너리가 비어있으므로 전기용품종류: 사용되는 순서를 넣는다. 2:0 을 넣는다.
3	1	{2:0, 3:1}	플러그의 구멍이 비어있으므로 3:1 을 넣는다.
2	2	{2:2, 3:1}	2는 이미 꽂혀있으므로 순서만 갱신해준다.
3	3	{2:2, 3:3}	마찬가지로 3도 이미있으므로 순서만 갱신한다.
1	4	{1:4 , 2:2}	플러그가 꽉차있으므로 하나를 빼야한다. 2는 다음 등장이 5번에서 있고, 3은 다음등장이 없으므로(inf 이므로) 더 큰값인 3을 뽑고 1:4를 넣는다.
2	5	{1:4 ,2:5}	2는 이미 꽂혀있으므로 순서만 갱신해준다.
7	6	{2:5, 7:6}	이미 꽃혀있는 1,2 모두 다음등장이 inf이므로 앞에 있는 1을 뽑고 7:6을 넣는다.

 

 

n, k = list(map(int,input().split()))
names = list(map(int,input().split()))

order = [[] for _ in range(k+1)]
INF = 10**16

# 각 전기용품 인덱스 저장 배열 생성
for i in range(k):
    order[names[i]].append(i)
for i in range(1,k+1):
    order[i].append(INF)

plug = {}

answer = 0

for i in range(k):
    cur = names[i]
    
    # 이미 있는 경우
    if cur in plug:
        plug[cur] += 1
        continue

    # 새로 꽂는 경우
    if len(plug)<n:
        plug[cur] = 0
        
    # 뽑고 꽃는 경우
    else:
        key = -1
        farthest = -1
        for x,t in plug.items():
            if farthest < order[x][t+1]:
                farthest = order[x][t+1]
                key = x

        del plug[key]
        plug[cur] = order[cur].index(i)
        answer += 1

print(answer)