백준 13414번: 수강신청

백준 13414번: 수강신청

import sys
input = sys.stdin.readline
K,L = map(int,input().split())
student_set={}
#1<=L<=500,000, 0<=K<=100,000에 1초 : O(N)
for i in range(L):
    std = input()
    if(std in student_set.keys()):
        student_set.pop(std)
    student_set[std] = i
check = 0
arr = list(student_set.items())
for i in range(min(K, len(arr))):
    print(arr[i][0].rstrip())

일단 1<=L<=500,000이고 0<=K<=100,000이므로 최대 O(N)의 알고리즘이어야겠다라는 생각을 했다. 그러니 단순히 queue로 넣고 빼고 하는 건 안 될 거라고 생각했고.. 처음에 짰던 알고리즘은 다음과 같다.

import sys
from collections import deque
input = sys.stdin.readline
K,L = map(int,input().split())
arr = deque()
student_set={}
#1<=L<=500,000, 0<=K<=100,000에 1초 : O(N)
for i in range(L):
    std = input()
    student_set[std] = i
    arr.append(std)
check = 0
for i in range(L):
    if(student_set[arr[i]]==i):
        check += 1
        print(arr[i])
    if(check==K):
        break

하지만 시간초과가 났다(...) dictionary에 값 집어넣는 것, 값 찾는 것, 배열에 값을 넣는 것은 O(1)인데 왜 오류가 나지.. 라고 생각했는데 알고보니 deque의 검색이 O(N)이었다(....) 그래서 O(N^2)가 되니까 시간초과가 되는 거였다.

import sys
input = sys.stdin.readline
K,L = map(int,input().split())
arr = []
student_set={}
#1<=L<=500,000, 0<=K<=100,000에 1초 : O(N)
for i in range(L):
    std = input()
    student_set[std] = i
    arr.append(std)
check = 0
for i in range(L):
    if(student_set[arr[i]]==i):
        check += 1
        print(arr[i])
    if(check==K):
        break

이렇게 deque 대신 리스트를 사용해서 작성해주면 시간초과가 나지 않는다! 삽입/삭제가 빈번할때는 리스트보다 deque가 낫지만, 검색이 많을때는 deque보다 리스트가 낫다. 이 부분을 명심해야 할 것...
그리고 맨 처음에 작성했던 코드로 되돌아가면, dictionary의 pop, insert는 모두 시간복잡도가 O(1)이다. 그리고 dictionary는 저장순서를 보장 (python 3.6부터!) 해주기 때문(python 3.6이전에는 OrderedDict를 사용해야 저장순서를 보장해줌.)에, pop()을 통해서 저장 순서를 보장해주고 그 후에 item()에 들어있는 값들을 최대 K개까지 출력해주면 된다. (items말고 keys로 해도 될듯 하다)