1713번: 후보 추천하기
첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대
www.acmicpc.net
문제
월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.
- 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
- 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
- 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
- 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
- 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.
입력
첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.
출력
사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.
코드
from heapq import heappop, heappush, heapify
n = int(input())
r = int(input())
frame = []
# 학생 게시
def add(student, num): # 학생번호, 추천순서
# 비어있는 사진틀이 없음
if len(frame) == n:
heappop(frame)
heappush(frame, [1, num, student]) # 추천횟수, 추천순서, 학생번호
for idx, student in enumerate(list(map(int, input().split()))):
find = False
# 이미 게시된 학생인지 확인
for i in range(len(frame)):
if student == frame[i][2]:
frame[i][0] += 1 # 추천 횟수 증가
heapify(frame)
find = True
break
# 아직 게시되지 않은 학생이라면
if not find:
add(student, idx)
# 학생 출력
frame.sort(key = lambda x:x[2])
for i in range(len(frame)):
print(frame[i][2], end=" ")
- enumerate 함수는 파이썬의 내장함수로, 인덱스, 원소로 이루어진 튜플을 만들어준다.
- frame 배열은 최소힙 자료구조를 이용하여 추천횟수 - 추천순서 순서로 정렬되도록 하였는데 출력 시에는 학생 번호 오름차순으로 정렬되어야 하므로 sort함수를 이용하여 lambda식을 통해 다시 정렬해주었다.
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 20291번 파일 정리 (0) | 2023.04.23 |
---|---|
[Python/파이썬] 백준 12933번 오리 (0) | 2023.04.22 |
[Python/파이썬] 백준 5212번 지구 온난화 (0) | 2023.04.21 |
[Python/파이썬] 백준 20436번 ZOAC 3 (0) | 2023.04.20 |
[Python/파이썬] 백준 10994번 별 찍기 - 19 (0) | 2023.04.19 |