테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 수강신청 ======

===== 풀이 =====
  * 시키는대로 구현할 생각을 해보자. 대기목록을 리스트로 관리하면, 대기열에 있는 학생을 뒤로 보내는 연산을 할때 O(K) 시간복잡도가 걸리므로 문제가 된다.
  * 각 학생에 대해서 대기 순서를 저장하는 딕셔너리를 이용해서 관리해보자. 대기열에 있는 학생을 맨 뒤로 보내는 것은 딕셔너리에서 학생에 대한 순서를 현재 대기열의 길이로 업데이트하는 것만으로 처리되므로 O(1)에 업데이트가 된다. 업데이트가 모두 끝나면, 순서를 기준으로 정렬해서 앞의 K명을 출력하면 된다, 딕셔너리를 처리하는데 O(n), 그 뒤에 정렬하는데에 O(nlogn), 출력에 O(K). 총 시간복잡도는 O(nlogn +K가 된다)
  * 이것보다 더 효율적인 방법은, 데이터를 뒤에서부터 처리하는 것. 이경우에는 중복된 학생이 등장할 경우 순서를 바꿔줄 필요 없이 그냥 앞에 나온 것을 무시해버리면 된다. 정렬과정이 생략되므로 시간복잡도는 O(n+K). K<=n 이므로 실제로는 그냥 O(n)
  * 이것을 구현하기 위해서는, 학생의 중복 여부를 체크하기 위한 set과 순서를 저장하기 위한 list를 같이 사용하는 것이 쉽게 떠오르는 방법이다. 하지만, 최신 파이썬 버전에서는 딕셔너리가 입려된 순서를 보장하도록 되어있으므로 그냥 딕셔너리를 사용하면 중복여부 체크와 순서 저장을 동시에 할수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 13414. 수강신청".

- Problem link: https://www.acmicpc.net/problem/13414
- Solution link: http://www.teferi.net/ps/problems/boj/13414
"""

import sys


def main():
    K, L = [int(x) for x in sys.stdin.readline().split()]
    student_ids = [sys.stdin.readline().rstrip() for _ in range(L)]
    waiting_set = {}
    for student_id in reversed(student_ids):
        if student_id not in waiting_set:
            waiting_set[student_id] = True
    print('\n'.join(x for x, _ in zip(reversed(waiting_set), range(K))))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}