[그리디] 백준 1700번: 멀티탭 스케줄링 / 골드1

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

1700번: 멀티탭 스케줄링

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전

www.acmicpc.net

import collections
n, k = map(int, input().split())
order = collections.deque(list(map(int, input().split())))

holes = [0]*n
count = -n
while order:
    elem = order.popleft()
    if elem not in holes:
        # one device should be pulled out
        distance = [101]*n
        for i in range(len(holes)):
            for j in range(len(order)):
                # measure distance
                if order[j] == holes[i]:
                    distance[i] = j
                    break

        idx = distance.index(max(distance))
        holes[idx] = elem
        count += 1

print(max(count, 0))

플러그를 뽑아야 할 상황이 생겼을 때 꽃혀있는 기기 중 가장 나중에 다시 쓰는 기기를 빼주면 된다.

데크를 이용하여 큐를 구현하였다.

처음 count를 -n으로 해주는 이유는 처음 n개가 꽃힐 때는 플러그를 빼지 않아도 되기 때문이다.