파이썬 백준 1700 멀티탭 스케줄링

import sys
input = sys.stdin.readline
 
n, k = map(int, input().split())
plug = list(map(int, input().split()))
 
cons = [0 for i in range(n)]
count = 0
for now in range(k) : 
    TF = False
    for i in range(n) : 
        if cons[i] == 0 or cons[i] == plug[now] : 
            cons[i] = plug[now]
            TF = True
            break
    if TF : 
        continue
    count = count + 1
    lastidx = 0
    for i in range(n) : 
        try : 
            if lastidx < plug[now:].index(cons[i]) : 
                lastidx = plug[now:].index(cons[i])
                last = i
        except : 
            cons[i] = plug[now]
            TF = True
            break
    if TF : 
        continue
    cons[last] = plug[now]
print(count)

IDEA

콘센트가 비었다면 그냥 꽂으면 된다.

콘센트가 꽉 찼다면 이후의 스케줄을 보아 안쓰는 플러그를 뽑으면 된다.

콘센트가 꽉 찼는데 안쓰는 플러그도 없다면 가장 나중에 쓰는 플러그를 뽑으면 된다.

이를 코드로 구현한다.

 

line 9 ~ 18

먼저 콘센트가 꽉 찰때까지 플러그를 꽂는다.

꽂는데 성공하면 이후의 코드를 실행시키지 않고 continue한다.

빈 곳이 없고 이미 꽂힌 플러그도 아니라면 뭔가 하나를 뽑아야 하므로 일단 count를 +1하고 아래를 진행한다.

 

line 19 ~ 31

콘센트에 꽂힌 각각의 플러그(cons[i])에 대해 for문을 돌린다.

이후의 스케줄(plug[now:])를 보아 cons[i]가 없다면 try문에서 index함수가 돌아가지 않아 에러가 뜨고 except로 간다. 이 cons[i]는 다시 쓰이지 않는 플러그이므로 뽑고 그자리에 plug[now]를 꽂는다.

만약 모든 cons[i]가 이후로도 쓰이는 플러그라면 그중 가장 나중에 쓰이는 것을 뽑아야 한다.

try문 안에서 기록한 index의 최댓값 last를 이용하여, except break 없이 for문이 끝까지 돌았다면 가장 늦게 쓰이는 cons[last]를 뽑고 그자리에 plug[now]를 꽂는다.