문제
N개의 사진틀에 후보를 추천한다. 이미 게시된 후보를 추천하면 추천수가 증가한다. 빈 자리가 없으면 추천수가 가장 적은 후보를 제거하고(동률이면 가장 오래된 후보) 새 후보를 게시한다. 최종 게시 후보를 오름차순 출력한다.
입력
사진틀 수 N, 추천 횟수, 추천 학생 번호들이 주어진다.
출력
최종 게시된 후보 번호를 오름차순으로 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 9 2 1 4 3 5 6 2 7 2 | 2 6 7 |
풀이
리스트로 사진틀을 관리하며 추천 시뮬레이션을 수행한다.
- 추천 학생이 이미 사진틀에 있으면 해당 추천수를 1 증가시킨다
- 사진틀에 없고 자리가 꽉 차면, 추천수가 최소인 후보를 제거한다 (동률이면 리스트 앞쪽 = 가장 오래된 후보)
- 새 후보를 리스트 끝에 추가하고 추천수를 1로 설정한다
- 모든 추천 처리 후 사진틀을 정렬하여 출력한다
핵심 아이디어: 리스트의 삽입 순서가 곧 게시 시점이므로, min() 탐색 시 가장 먼저 발견되는 최솟값이 가장 오래된 후보이다.
코드
N = int(input())
Vote = int(input())
students = list(map(int, input().split()))
picture = []
score = []
for i in range(Vote):
if students[i] in picture:
for j in range(len(picture)):
if students[i] == picture[j]:
score[j] += 1
else:
if len(picture) >= N:
for j in range(N):
if score[j] == min(score):
del picture[j]
del score[j]
break
picture.append(students[i])
score.append(1)
picture.sort()
print(' '.join(map(str, picture)))복잡도
- 시간: O(V * N) — V는 추천 횟수, 매번 사진틀 N개 탐색
- 공간: O(N) — 사진틀 리스트