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

[백준] 1700. 멀티탭 스케줄링 - 파이썬

 

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

1700번: 멀티탭 스케줄링

 

풀이

플러그를 새로 꽂을 때마다 경우의 수가 나눠지는데

1. 플러그 자리가 남아 있을 때
2. 꽂혀 있는 기기를 그대로 사용
3. 플러그 하나를 빼야 함.

1, 2번은 그냥 처리하면 되고,

3번을 처리하는 방법이 문제다.

Greedy하게 처리하자면, 앞으로 쓸 일이 없거나, 가장 나중에 사용할 기기를 빼는 것이 최선이므로, 그렇게 처리함.

 

from collections import deque
import sys
read = sys.stdin.readline
 
def index(x):
    if x not in elecs:
        return -1
    else:
        return elecs.index(x)
 
N, k = map(int, read().strip("\n").split())
elecs = list(map(int, read().strip("\n").split()))
 
tap = deque([])
eleclist = elecs[:]
elecs = deque(elecs)
answer = 0
 
for elec in eleclist:
    if elec in tap:
        elecs.popleft()
        continue
    elif len(tap) < N:
        tap.append(elecs.popleft())
    else:
        lastindex = 0
 
        for n in tap:
            j = index(n)
            if j == -1:
                tap.remove(n)
                lastindex = -1
                break
            else:
                if j > lastindex:
                    lastindex = j
 
        if lastindex != -1:
            tap.remove(elecs[lastindex])
 
        tap.append(elecs.popleft())
        answer += 1
 
print(answer)