[BOJ 1700] 멀티탭 스케줄링(Python)

문제

멀티탭 스케줄링

---

문제 해설

이 문제는 여러 페이징 기법 중 OPT(Optimal Replacement, 최적 교체)를 활용하여 푸는 문제입니다.
OPT란 앞으로 일어날 page fault정보를 예측하여 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법입니다.

OPT는 앞으로 일어날 일을 알 수 없기 때문에 현실적으로는 쓸 수 없지만, 사용하게 된다면 페이징 기법 중 가장 효율적인 기법입니다. OPT를 사용할 수 있는 이유는 미리 멀티탭에 꽂을 순서가 정해져 있기 때문입니다.

1. 멀티탭에 자리가 있으면 그냥 꽂습니다. 단, 이미 동일한 플러그가 꽂혀있는 경우 continue
2. 멀티탭에 자리가 없어 플러그를 뽑아야 하는 상황입니다.
   2-1. 만약 현재 꽂혀있는 플러그 중 앞으로 쓰이지 않는 것이 있다면 뽑습니다.
   2-2. 그런 플러그 조차 없다면 가장 나중에 쓰이는 플러그를 뽑습니다.

---

풀이 코드

# 2:44
n, k = map(int, input().split())
# 다음 멀티탭에 꽂을 제품들
items = list(map(int, input().split()))
answer = 0
# 현재 꽂혀있는 제품들
frame = []


def check(i):
    # 앞으로 안쓰이는 것이라면 뽑는다.
    # 모두 쓰이는 것이라면 가장 나중에 쓰이는 것을 뽑는다.
    target = 0
    idx = -1
    for f in frame:
        if f not in items[i:]:
            return f
        if idx < items[i:].index(f):
            target = f
            idx = items[i:].index(f)
    return target


for i in range(k):
    # 멀티탭에 자리가 있으면 그냥 꽂는다.
    if len(frame) < n:
        if items[i] in frame:
            continue
        frame.append(items[i])
        continue
    # 플러그를 무언가 뽑아야 하는 상황이다.
    if items[i] not in frame:
        frame[frame.index(check(i))] = items[i]
        answer += 1
print(answer)

---