[파이썬/Python] 백준 1713번: 후보 추천하기

숨·2024년 8월 27일

📌 문제 탐색하기

N : 사진틀의 개수 $(1 ≤ N ≤ 20)$
recommendations : 총 추천 횟수 $(0 ≤ recommendations ≤ 1,000)$
students : 학생 번호 $(1 ≤ students ≤ 100)$

사진틀에 사진을 남길 수 있는 최종 후보가 누구인지 번호를 오름차순으로 출력하는 문제이다.

문제 풀이

⭐️ 사진틀 게시 & 추천받은 횟수 표시 규칙

추천 시작 전 모든 사진틀 빈 상태

추천 받은 학생의 사진 → 반드시 사진틀 게시되어야 함

빈 사진틀 ❌ → 추천 받은 횟수 가장 적은 학생 사진 삭제 후 게시

가장 적은 학생 2명 이상이라면 가장 오래된 사진 삭제

사진 삭제 → 해당 학생의 추천 횟수 0으로 변경

학생 번호를 키로 하는 딕셔너리를 정의한다.

학생의 추천 횟수, 추가된 시간을 딕셔너리에 추가한다.
"학생 번호" : [추천 횟수, 추가된 시간] 형태로 딕셔너리에 추가되도록 한다.

입력 받은 for문을 통해 추천 받은 학생 번호에 접근한다.
1. 사진틀에 학생 ⭕️
1-1. 추천 횟수를 1 증가
2. 사진틀에 학생 ❌
2-1. 사진틀에 자리 ⭕️ → 딕셔너리에 [1, 추가된 시간] 추가
2-2. 사진틀에 자리 ❌ → 추천 횟수 가장 적은 학생 찾기
2-2-1. 1명이면 삭제 후 "학생 번호" : [추천 횟수, 추가된 시간] 추가
2-2-2. 2명 이상이면 인덱스 적은 요소 삭제 후 "학생 번호" : [추천 횟수, 추가된 시간] 추가

가능한 시간복잡도

사진틀의 학생 정렬 → $O(NlogN)$
전체 학생 추천 횟수 내에서 문제 구현 → $O(recommendations * NlogN)$

최종 시간복잡도
총 $O(recommendations * NlogN)$ 로 최악의 경우 $O(1000 * 20 * log(20)$ 으로 2초 내 연산 가능하다.

알고리즘 선택

for문으로 추천받은 학생에 접근해서 사진틀 딕셔너리에 넣고 빼기

📌 코드 설계하기

N 입력
전체 추천 횟수 입력
추천받은 학생 번호 입력
사진틀 딕셔너리 정의
사진틀에 학생 있는지 여부, 자리 여부에 따라 구현
오름차순 정렬
결과 출력

📌 시도 회차 수정 사항

1회차

사진틀에서 오래된 학생을 먼저 제거한다는 말에 큐로 구현해서 바로 popleft()하면 되겠다고 생각해서 구현했는데 우선 순위가 추천 수, 사진틀에 오래 있는 학생인 것을 간과했다.
따라서 제외할 학생을 찾을 때 저 2가지 기준에 따라 정렬할 수 있도록 따로 리스트를 정의해 그 안에서 제외하려고 했다.
잘 되지 않았다.

2회차

사진틀에 대한 정보를 큐를 통해 관리하려고 했는데 정렬이나 값 접근하는 면에 있어서 어려움이 있었다.
딕셔너리로 변경하고 학생 번호를 키, 추천 횟수 & 추가 시간을 값으로 해서 저장하도록 변경했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N 입력
N = int(input())

# 전체 추천 횟수 입력
recommendations = int(input())

# 추천 받은 학생 번호 입력
selected_students = list(map(int, input().split()))

# 사진틀 딕셔너리 정의
frames = dict()

for i in range(recommendations):
    # 사진틀에 학생 있는지 확인
    if selected_students[i] in frames:
        # 있는 학생이면 추천 횟수 증가
        frames[selected_students[i]][0] += 1
    else:
        # 자리가 있다면 추가
        if len(frames) < N:
            frames[selected_students[i]] = [1, i]
        # 자리가 없다면 추천 횟수 적은 사람 찾기
        else:
            # 추천 횟수, 추가된 시간 기준 정렬 (리스트로 변환)
            out_list = sorted(frames.items(), key=lambda x: (x[1][0], x[1][1]))
            # 학생 제거
            out_student = out_list[0][0]
            del(frames[out_student])
            # 새로운 학생 추가
            frames[selected_students[i]] = [1, i]

# 번호 오름차순으로 정렬
nums = list(sorted(frames.keys()))

# 결과 출력
print(" ".join(map(str, nums)))