BOJ 1713 : 후보 추천하기 (Python)

🔷 문제번호: 후보 추천하기 (BOJ 1713) Python

✅ 문제설명

월드초등학교 학생회장 후보를 추천으로 뽑습니다.
추천받은 학생들의 사진을 게시할 사진틀이 있고, 다음 규칙을 따릅니다:

• 학생이 추천을 받으면 반드시 사진틀에 올라가야 합니다.
• 이미 게시된 학생이면 추천 수만 증가합니다.
• 비어있는 자리가 없으면,
• 추천 수가 가장 적은 학생을,
• 여러 명이면 게시된 지 가장 오래된 학생을 제거합니다.
• 새로운 학생이 올라가면 추천 수는 1, 게시 시각은 현재 시간입니다.
• 마지막에 사진틀에 올라간 학생들을 오름차순으로 출력합니다.

✅ 아이디어

• 추천 수, 게시 시각, 게시 여부를 관리하는 구조체를 각 학생 번호에 연결합니다.
• 사진틀에 올라간 학생 목록은 따로 배열로 관리합니다.
• 추천을 하나씩 처리하면서:
• 이미 게시된 학생이면 추천 수만 증가
• 아니라면:
• 사진틀이 비어 있으면 추가
• 가득 찼으면 추천 수 + 게시 시각 기준으로 한 명 제거 후 추가
• 마지막에는 게시 중인 학생 번호만 오름차순 정렬해서 출력합니다.

✅ 전체코드

class Person:
    def __init__(self):
        self.reco = 0
        self.time = 0
        self.in_frame = False

N = int(input())  # 사진틀 개수
M = int(input())  # 추천 횟수
data = list(map(int, input().split()))  # 추천받은 학생 목록

arr = [Person() for _ in range(101)]  # 1~100번 학생
frame = [0] * N  # 사진틀
frame_size = 0
current_time = 0

for k in data:
    if arr[k].in_frame:
        arr[k].reco += 1
        continue

    if frame_size < N:
        frame[frame_size] = k
        frame_size += 1
        arr[k].reco = 1
        arr[k].time = current_time
        arr[k].in_frame = True
        current_time += 1
    else:
        # 제거 대상 찾기
        target = frame[0]
        for i in range(1, N):
            now = frame[i]
            if arr[now].reco < arr[target].reco:
                target = now
            elif arr[now].reco == arr[target].reco and arr[now].time < arr[target].time:
                target = now

        # target 제거
        arr[target].reco = 0
        arr[target].in_frame = False

        # frame 내 위치 교체
        for i in range(N):
            if frame[i] == target:
                frame[i] = k
                break

        arr[k].reco = 1
        arr[k].time = current_time
        arr[k].in_frame = True
        current_time += 1

# 출력
for i in range(1, 101):
    if arr[i].in_frame:
        print(i, end=' ')

✅ 분해설명

1. 자료 구조 준비

• Person 클래스는 학생 정보를 저장합니다.
• 추천 수 (reco)
• 게시된 시간 (time)
• 사진틀에 있는지 여부 (in_frame)
• arr[101] 배열로 학생 번호 1~100을 관리합니다.
• frame[N] 배열로 사진틀에 올라온 학생 번호를 저장합니다.

2. 추천 처리 로직

• 추천받은 학생이 게시 중이라면:
• 추천 수만 증가하고 다음으로 넘어감
• 게시 중이 아니라면:
• 사진틀에 자리가 있으면 → 바로 넣고 시간 저장
• 사진틀이 꽉 찼으면:
• 추천 수가 가장 적고,
• 같으면 게시 시간이 오래된 학생을 target으로 정함
• 그 자리에 새로운 학생을 넣음

3. 출력

• 학생 번호 1~100을 순회하면서
• 사진틀에 올라와 있는 학생만 print로 출력
• 자동 정렬 효과 발생 (1~100 순서대로 검사하므로)