1700. 멀티탭 스케줄링 (Python)

1700번: 멀티탭 스케줄링

 

풀이

 페이지 교체 알고리즘 중 하나인 OPT(Optimal Replacement, 최적 교체)를 생각하면 된다. 일단 멀티탭 구멍에 맞게 각 전기용품을 꽂은 다음 현재 멀티탭에 없는 전기용품을 사용해야 할 경우 멀티탭을 사용 중인 용품 중 가장 먼 미래에 사용될 용품의 플러그를 빼고 새로운 용품의 플러그를 꽂도록 구현해주면 된다. 

 

코드

import sys

# 제거해야 할 전기용품을 찾기 위한 함수


def removePlug(idx):
    maxIdx = -1
    item = -1

    for plug in plugs:  # 멀티탭에 꽂아 놓은 전기용품 중
        try:
            tmpIdx = items.index(plug, idx)  # 현재 순서 이후에 언제 등장하는지를 찾는다.

            if tmpIdx > maxIdx:  # 가장 늦게 사용될 전기용품을 제거하도록 설정해준다.
                maxIdx = tmpIdx
                item = plug
        except:  # 만약 현재 순서 이후 사용되지 않는 전기용품이라면 바로 해당 전기용품을 제거하도록 해주면 된다.
            return plug

    return item


if __name__ == '__main__':
    N, K = map(int, input().split())  # N: 멀티탭 구멍의 개수, K: 전기 용품의 총 사용횟수
    items = list(map(int, input().split()))  # 전기용품 사용 순서 리스트

    if N >= K:  # 멀티탭 구멍이 전기 용품의 수 이상일 경우 플러그를 빼지 않아도 된다.
        print(0)
        sys.exit()

    plugs = []  # 현재 멀티탭에 꽂아 사용 중인 전기용품의 리스트
    res = 0  # 플러그 제거 횟수

    for i in range(K):
        item = items[i]

        # 아직 멀티탭에 사용할 수 있는 구멍이 있고 현재 전기 용품이 사용중이지 않을 경우
        # 제거할 필요 없이 꽂아서 사용하면 된다.
        if len(plugs) < N and item not in plugs:
            plugs.append(item)
            continue

        # 멀티탭에 남은 구멍이 없고 멀티탭에 없는 전기용품일 경우
        if item not in plugs:
            plugForRemove = removePlug(i)  # 제거해야 할 전기용품을 찾아서
            plugs.pop(plugs.index(plugForRemove))  # 해당 전기용품을 plugs에서 제거해주고
            plugs.append(item)  # 새로운 전기용품을 꽂는다.
            res += 1  # 플러그 제거 횟수 증가

    print(res)