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

1700번: 멀티탭 스케줄링

풀이 방법

• 반복문으로 전기용품을 하나씩 방문하면서 플러그를 빼야하는지 안 빼도 되는지 체크한다.
• 플러그가 N개 이하로 꽂혀있거나, 현재 확인하려는 전기용품이 이미 꽂혀있다면 뽑지 않아도 된다.
• 뽑아야할 때, 꽂혀있는 플러그 중에서 이후 가장 나중에 사용되는 전기용품 또는 이후 사용되지 않는 전기용품을 먼저 뽑는다.
• N과 K모두 100이하 이므로 시간초과에 대해서 생각하지 않아도 된다. 

전체 코드

n, k = map(int, input().split())
arr = list(map(int, input().split()))
plugin = []
answer = 0
for i in range(k):
    if arr[i] in plugin:
        continue
    if len(plugin) < n:
        plugin.append(arr[i])
        continue
     
    # 플러그를 뽑아야 함
    answer += 1
    out = 0  # 뽑을 플러그
    outidx = 0  # out이 이후 몇 번째에 사용되는지 (arr에서 인덱스)
    for j in range(n):
        try:
            idx = arr[i+1:].index(plugin[j])
            if idx > outidx:
                out = j
                outidx = idx
        except: 
        # 이후 사용되지 않는 플러그가 있다면 걔를 뽑으면 된다.
            out = j
            break
    plugin[out] = arr[i]
print(answer)