[Python] 백준 1700번 - 멀티탭 스케줄링

문제 https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

그리디 오랜만에 풀어서 어려웠다... 골드1이기도 했고......

 

구조를 잡는 것부터 어려웠다.

빈 콘센트가 존재하는 경우 플러그를 꽂고, 이미 해당 기기가 꽂혀있는 경우에는 다시 꽂지 않아야 한다.

 

콘센트가 꽉 차 있고, 해당 기기가 꽂혀있지 않은 경우에는 두 가지를 고려해야 한다.

1. 멀티탭에 꽂혀있는 기기들 중 이후에 재사용하는 기기가 없는 경우
2. 재사용하는 기기가 있는 경우

 

1번의 경우 재사용하지 않는 기기를 콘센트에서 뽑고 현재 제품을 꽂는다.

 

2번 경우에는 가장 나중에 재사용하는 기기를 찾아야 한다.

현재 기기가 가장 나중에 재사용하는 기기인 경우로 elif문을 걸어서 가장 나중에 사용하는 제품을 뽑고 현재 제품을 꽂는다. (현재 기기보다 나중에 재사용하는 기기가 있는 경우에는 나중에 재사용하는 기기를 뽑을 것이기 때문에 고려하지 않아도 됨).

 

전반적인 틀은 이렇다.

세부적인 내용들은 풀면서 주석으로 적었다. 

나중에 다시 봐도 잘 이해가 되겠지...? 그래야 한다.

 

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
elec = list(map(int, input().split()))
mt = [0]*n #multitap
ans = 0
last = 0 #가장 나중에 재사용하는 제품

for i in range(k):
    product = elec[0]
    if product in mt: #이미 꽂혀있는 경우
        elec.remove(product)
        continue
    elif 0 in mt: #빈 콘센트 존재
        mt[mt.index(0)] = product
        elec.remove(product)

    else: #위에 if문에 해당하지 않는 경우 기존 플러그를 뽑아야 함 (콘센트 만석)
        for j in mt:
            #멀티탭에 꽂혀있는 제품들 중 이후에 재사용하는 제품이 없는 경우
            if j not in elec: 
                change = j #재사용하지 않는 제품이 있으므로 이 제품을 뽑고 현재(i) 플러그를 꽂는다.
                break
                
            elif elec.index(j) > last: #현재 제품(j)이 가장 나중에 재사용하는 제품인 경우
                #가장 나중에 사용하는 제품을 뽑고 현재 제품을 꽂는다.
                last = elec.index(j)
                change = j #우선 여기서 바꾸기로 함 
                #그러나, for j in mt 문을 돌면서 이후에 재사용하지 않는 제품이 콘센트에 꽂혀져있다면 그 제품을 뽑을 것

        mt[mt.index(change)] = product #바꾸기로 한 제품(change)이 꽂혀있는 콘센트에 현재 제품(product)을 꽂는다.
        elec.remove(product)
        last = 0 
        ans += 1

print(ans)