[백준] 13414번 - 수강신청

1. 문제 요약

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

수강신청 시스템에서 학생들이 신청을 한다.

• 총 L명의 신청 기록이 주어짐
• 같은 학생이 여러 번 신청할 수 있음
• 같은 학생이 여러 번 신청하면 마지막 신청만 유효

문제를 처음 보고 든 생각

이 문제는 수강신청 대기 명단처럼 보였다.
학생들이 순서대로 신청을 하는데, 같은 학생이 여러 번 신청할 수 있고 마지막 신청만 유효하다는 점이 핵심이었다.

즉, 단순히 입력을 그대로 저장하는 문제가 아니라

• 중복된 학번을 처리해야 하고
• 마지막 신청 기준으로 순서를 다시 판단해야 한다

는 특징이 있었다.

처음에는 큐처럼 순서를 관리하면 될 것 같아서 deque를 떠올렸다.

---

2. 처음 시도: deque로 직접 중복 제거하기

처음에는 신청 순서를 그대로 넣고,
이미 들어온 학번이 다시 들어오면 기존 값을 지우고 뒤에 다시 넣는 방식으로 생각했다.

하지만 구현하면서 문제가 생겼다.

 1) deque는 중간 삭제가 불편하다

popleft()는 맨 앞 원소만 제거할 수 있는데,
내가 원했던 건 중간에 있는 특정 학번 제거였다.

즉,

• 맨 앞 삭제는 쉬움
• 맨 뒤 삭제도 쉬움
• 중간 원소 삭제는 비효율적이고 구현도 어색함

이라는 문제가 있었다.

 2) 순회하면서 삭제하려다 로직이 꼬였다

큐를 순회하면서 같은 학번을 찾고 제거하려고 했는데,
삭제와 탐색을 동시에 하면 인덱스가 꼬이기 쉽다.

결국 이 문제는 “큐처럼 보이지만 큐로 풀기 좋은 문제는 아니구나”라는 걸 느꼈다.

---

3. 관점을 바꾼 핵심

문제를 다시 보면 실제로 필요한 건 이거였다.

각 학번에 대해 마지막으로 등장한 위치만 기억하면 된다.

앞의 신청 기록은 마지막 신청이 들어오는 순간 의미가 사라진다.
그러면 굳이 큐 안에서 이전 값을 찾아 제거할 필요가 없다.

그냥

• 학번을 key로 저장하고
• 마지막 등장 순서를 value로 저장한 뒤
• 마지막 순서 기준으로 정렬

하면 된다.

이 순간 dict가 훨씬 적절하다는 걸 알게 됐다.

---

4. 최종 코드

import sys
input = sys.stdin.readline

k, l = map(int, input().split())

ready = dict()
for i in range(l):
    person = input().rstrip()
    ready[person] = i

result = sorted(ready.items(), key=lambda x: x[1])

count = 0
for p in result:
    if count == k:
        break
    print(p[0])
    count += 1

 

---

5. 코드 풀이

 1) 마지막 신청만 남기기

 

ready[person] = i

 

같은 학번이 여러 번 들어오더라도 딕셔너리에서는 key가 하나만 유지된다.
따라서 같은 학번이 다시 들어오면 이전 값은 덮어쓰기 되고, 결과적으로 마지막 신청 순서만 남는다.

예를 들어, A B A C 라면 A는 처음 신청 기록이 아니라 마지막에 들어온 위치로 갱신된다.

---

 2) 마지막 신청 순서 기준 정렬

result = sorted(ready.items(), key=lambda x: x[1])

 

ready.items()는 (학번, 마지막 순서) 형태로 들어 있다.
이걸 마지막 순서 기준으로 오름차순 정렬하면
실제로 최종 대기열 순서가 된다.

---

 3) 앞에서부터 k명 출력

 

count = 0
for p in result:
    if count == k:
        break
    print(p[0])
	count += 1

정렬된 결과에서 앞쪽부터 최대 k명만 출력하면 된다.