문제

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

풀이

첫 번째 생각

순서대로 살펴보면서 이미 존재하는 학번이 나온다면 그 전에 나왔던 위치까지 되돌아가는 과정을 stack 자료구조를 통해 풀이
-> 아마도 대기목록의 길이가 500,000이나 되기 때문에 시간초과 가능성이 다분하다. 실제로 이런식으로 진행해봤더니 TLE가 나옴을 확인할 수 있었다.

두 번째 생각

딕셔너리를 통해 학번이 나올때마다 순서를 재정의 해준다.

dictionary[학번] = 순서

이렇게 하면 결국 각 학번애는 마지막으로 나온 순서가 저장되어있을 것이다.

최종적으로 순서를 기준으로 오름차순 정렬하여 k개의 학번을 앞에서부터 순서대로 출력해준다.

CODE

import sys
from collections import deque

input = sys.stdin.readline

k, l = map(int, input().split())
dq = deque([])
count = {}

for i in range(l):
    num = input().rstrip()
    count[num] = i

idx = 0

for num in sorted(count, key=lambda x: count[x]):
    if idx == k:
        break
    print(num)
    idx += 1