파이썬으로 풀어보는 백준 1700번: 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

 

 

내 풀이:

N, K = map(int,input().split())
sequence = list(map(int,input().split()))
history = [[] for _ in range(101)]
 
for idx, num in enumerate(sequence):
    history[num].append(idx)
 
socket = {}
 
ans = 0
for idx, num in enumerate(sequence):
    if len(socket) < N:
        socket[num] = 1
 
    elif num in socket:
        pass
 
    else:
        del_idx = idx
        del_num = 101
        for check in socket:
            for check_idx in history[check]:
                if check_idx > idx:
                    if del_idx < check_idx:
                        del_idx = check_idx
                        del_num = check
                    break
            else:
                del_num = check
                break
 
        del socket[del_num]
        socket[num] = 1
        ans += 1
 
print(ans)

Python3, 64ms

콘센트가 꽂혀있는 전자기기 번호들을 socket이라는 딕셔너리에 저장했다. 이후 해싱 효과를 노리고 history라는 리스트에 각 전자기기별 꽂아야 하는 순서를 저장하였다. 그러나 결과적으로는 history를 따로 만들지 않고 특정 인덱스 이후의 전자기기들을 검토하는 방법이 시간이 더 짧게 나오는 것을 확인할 수 있었다. 이번 문제는 전형적인 그리디 알고리즘 문제라고 할 수 있겠다.