[백준] 1700 멀티탭 스케줄링 파이썬

문제

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

1700번: 멀티탭 스케줄링

 

 

---

풀이

 

현재 탭에 꽂혀있는 제품 중 가장 나중에 사용되는 제품을 뽑는 그리디 문제였다.

next에 현재 스케줄 뒤로 제품별로 가장 빨리 사용되는 순번을 저장해놓는다.

멀티텝에 꽂힌 제품 중 next에서 가장 번호가 큰 것을 제거한다.

 

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

order = list(map(int, input().split()))
next = {}

for i in range(k):
    if order[i] not in next:
        next[order[i]] = i

def updateNext(i): #순번 업데이트
    global next
    if order[i] not in order[i+1:]:
        next[order[i]] = 101
    for j in range(i+1, k):
        if order[j] == order[i]:
            next[order[i]] = j
            break

mtap = []
answer = 0
for i in range(k):
    if order[i] in mtap: #이미 멀티텝에 있는 제품 사용
        updateNext(i)
        continue
    if len(mtap) < n: #멀티텝 자리가 비었음
        mtap.append(order[i])
        updateNext(i)
    else: #뽑고 새로 꽂는다
        temp = [(next[i], i) for i in mtap]
        temp.sort(reverse=True) #다음에 가장 늦게 사용되는 제품을 찾기 위해 정렬
        for j in temp:
            if j[1] in mtap:
                mtap.remove(j[1])
                break
        answer += 1
        mtap.append(order[i])
        updateNext(i)
print(answer)

근데 그냥 next만들 것 없이 새로 꽂을 때 바로바로 뒤에있는 것들 중 가장 나중에 사용되는 것 찾아도 됐을 것 같다.