[Python] Baekjoon - 1700. 멀티탭 스케줄링

백준 1700번 멀티탭 스케줄링 문제는 N구의 콘센트와 K개의 제품 사용 순서가 주어졌을 때 콘센트를 뽑는 최소 횟수를 구하는 문제다. 그리디 알고리즘을 사용해 해결할 수 있으며 난이도는 골드 1이다.

 

백준 1700번 멀티탭 스케줄링 문제 정보

알고리즘 분류

- 그리디 알고리즘

난이도

- 골드 1

 

멀티탭 스케줄링 문제 요약

• N구 콘센트와 제품 사용 순서(K개)가 주어졌을 때, 콘센트를 뽑는 최소 횟수 구하기

문제 풀이 방법

과정

• 매 순서마다, 콘센트가 모자라면 꼽혀있는 제품 중 뽑을 거 하나 골라야 함
• 앞으로 남은 리스트를 보고, 꼽혀있는 것 중 가장 나중에 필요한 제품의 콘센트 뽑기 (그리디)

풀이

• onPlug: 현재 콘센트에 꼽혀있는 제품 set
• rest: 각 제품별 남은 순서를 저장하는 dictionary
  • 더 이상 사용되지 않으면 INF 저장
• 매 순서마다 아래의 case로 나누어서 처리
  1. 콘센트에 이미 꼽혀있는 경우
  2. 콘센트 남아있는 경우
  3. 콘센트 꽉 차 있는 경우
     • 콘센트에 꼽혀있는 제품들 중 가장 나중에 사용하는(또는 사용이 끝난) 제품 뽑기
       -> dictionary 정렬 이용

 

코드

from collections import deque

INF = float('inf')


def getMinPlugChange():
    global N, K, readyQueue

    changeCnt = 0
    onPlug = set()
    rest = dict()

    # 각 제품의 task list 구하기
    for i, task in enumerate(readyQueue):
        if task in rest:
            rest[task].append(i)
        else:
            rest[task] = deque([i])
    # 추후 정렬을 위해 task 없는 제품에는 무한대 저장 
    for i in range(1, K+1):
        if i not in rest:
            rest[i] = deque([INF])

    for idx, nowTask in enumerate(readyQueue):
        # 이번 차례 제품이 콘센트에 꼽혀있지 않을 때 
        if nowTask not in onPlug:
            # 콘센트 자리 남아있는 경우 
            if len(onPlug) < N:
                onPlug.add(nowTask)
            # 콘센트 자리 없는 경우 
            else:
                # 콘센트에 꼽혀있는 제품들의 남은 task list 불러와서
                # 가장 나중에 사용하는 (또는 사용이 끝난) 제품 찾기 
                temp_dict = {key: value for key, value in rest.items() if key in onPlug}
                rank = sorted(temp_dict.items(), key=lambda item: item[1][0], reverse=True)
                deleted = rank[0][0]
                onPlug.remove(deleted)
                onPlug.add(nowTask)
                changeCnt += 1

        # 이번 차례 제품의 rest list 갱신 
        # 사용 끝났으면 무한대 넣어주기 
        rest[nowTask].popleft()
        if len(rest[nowTask]) == 0:
            rest[nowTask].append(INF)

    return changeCnt


if __name__ == '__main__':
    N, K = map(int, input().split())
    readyQueue = list(map(int, input().split()))
    print(getMinPlugChange())