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

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다.

상세보기

• 운영체제에서 배웠던 Optimal Algorithm을 구현하는 문제
• '가장 나중에 사용할 전자제품'을 뽑는 식으로 구현했다.
• 만약, 해당 전자제품이 더 이상 쓰지 않을 경우 우선적으로 뽑도록 설정하였다.

from sys import stdin; input=stdin.readline
from collections import deque
from collections import defaultdict

N, K = map(int,input().split())         # 멀티탭이 몇 구인지 나타내는 N, 전자제품의 사용 횟수 K
goods = defaultdict(deque)              # 각 물건의 사용순서를 담아둘 defaultdict 선언
nums = tuple(map(int,input().split()))  # 전자제품의 순서 tuple로 받기
tabs = []                               # 전자제품 꽂아두는 tab
cnt = 0                                 # 갈아끼우는 횟수 담아둘 cnt
for i in range(K):                      # nums 돌면서 나오는 인덱스를 goods에 채우기
    goods[nums[i]].append(i)

for i in range(K):                      
    if nums[i] in tabs:                 # 이미 꽂혀있다면 옮길 필요 없음
        goods[nums[i]].popleft()        # goods에선 꺼내줌
        continue
    if len(tabs) != N:                  # 아직 공간이 남아있으면
        tabs.append(nums[i])            # 꽂아주면 됨
        goods[nums[i]].popleft()
    else:                               # 공간이 없을 경우의 알고리즘 구현
        latest = -1                     # 가장 늦게 꽂는 순서
        latest_num = -1                 # 가장 늦게 꽂는 전자제품
        for n in tabs:                  # 돌면서 가장 늦게 꽂는 전자제품 확인하기
            if goods[n]:
                next = goods[n][0]
                if next > latest:
                    latest = next
                    latest_num = n
            else:                       # 만약에 goods가 비어있으면, 더 이상 쓰지 않는 전자제품이기 때문에 우선적으로 빼기
                latest_num = n
                break
        tabs.remove(latest_num)         # 가장 늦게 꽂는 전자제품 리스트에서 꺼내기
        tabs.append(nums[i])            # 새로 꽂아야 되는 전자제품 꽂기
        goods[nums[i]].popleft()
        cnt += 1

print(cnt)