[딕셔너리] boj 13414. 수강신청

문제 해석

이 문제는 N이 500,000까지이므로 우선 2중 for문을 사용하지 않겠다고 유념하고 덤벼야 한다.

이를 적용하기 위해 딕셔너리를 활용하였다. 어려운 문제는 사실 아닌 것 같고, 다른 풀이도 존재할 수 있지만, 개인적으로 나쁘지 않게 푼 것 같다.

풀이 코드

시간복잡도를 고려하지 않은 풀이

import sys
input = sys.stdin.readline


K, L = map(int, input().split())

li = []
for _ in range(L):
    s = input()
    if s in li:
        idx = li.index(s)
        li.pop(idx)
    li.append(s)
for i in range(K):
    print(li[i])

여기서 pop()과 index()의 내부 구현 로직에 따라 O(n)이므로, for문과 같이 돌리게 되면 O(n^2)이므로 시간을 초과하게 된다.

시간복잡도를 고려한 풀이

# 수강 가능 인원 K : 1 <= K <= 100,000
# 대기 목록 길이 L : 1< = L <= 500,000
import sys
input = sys.stdin.readline
from collections import defaultdict as dd


K, L = map(int, input().split())
dic = dd(int)
cnt = 0

for i in range(L):
    s = input().strip()
    dic[s] = i
swap_dic = {value : key for key, value in dic.items()}
li = sorted(swap_dic.keys(), key=lambda x : x)
for i in li:
    if cnt == K: break
    print(swap_dic[i])
    cnt += 1

위 풀이의 핵심은 반복문 등을 통해 dictionary를 사용하여 데이터 덮어쓰기를 통해 중복을 제거하면서 데이터를 뒤로 보내는 조건을 만족했다는 것이다.

또한 이후 출력을 용이하게 하기 위해 key와 value를 스왑해 주었다.

또 다른 참고할만한 풀이

import sys
from collections import OrderedDict

input = sys.stdin.readline

K, L = map(int, input().split())
queue = OrderedDict()

for _ in range(L):
    student_id = input().strip()
    if student_id in queue:
        del queue[student_id]
    queue[student_id] = None

cnt = 0
for student_id in queue:
    if cnt < K:
        print(student_id)
        cnt += 1
    else:
        break

이는 OrderedDict라는 자료구조를 사용하여 대기 목록을 관리하고, 대기 목록에서 학생을 제거하는 대신 기존 학생의 순서를 업데이트한다. 이렇게 하면 입력된 순서대로 정확한 결과를 출력할 수 있다.