★Greedy Upper-Advanced I - 1 Solved★

★ 1700 멀티탭 스케줄링 ★

 

❤️‍🔥 Optimal Page Replacement 알고리즘에서 콘센트에 처음으로 꼽는 page fault 횟수를 제외한 page fault의 횟수를 최소화하는 문제

 

❤️‍🔥 ① 콘센트 채우기 → ② 콘센트에 존재하지 않는 첫 기기 등장하면(page fault 상황) (1) 이미 채운 기기 중 아예 존재하지 않는 기기가 있다면 해당 기기와 교체 (2) 없다면 콘센트 기기의 index 확인해 가장 나중에 등장하는 기기와 교체(greedy)

import sys
input=sys.stdin.readline

N,K=map(int,input().split())
names=list(map(int,input().split()))
ans=0
ps=[0]*N #power_strip initialization
i=-1
while 1:
    i+=1
    if i==K:break
    if 0 in ps and names[i] not in ps: ps[ps.index(0)]=names[i]
    else:
        if names[i] not in ps:
            ans+=1
            flag=False
            for psn in ps:
                if psn not in names[i:]:
                    ps[ps.index(psn)] = names[i]
                    flag=True
                    break
            if not flag:
                idxs=[(psn,names[i:].index(psn)) for psn in ps]
                idxs = sorted(idxs,key=lambda x: x[1],reverse=True)
                ps[ps.index(idxs[0][0])] = names[i]
print(ans)

 

Optimal Page Replacement Algorithm

---