[골드 2] 백준 2461 - 대표 선수 (파이썬)

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

분류 : 정렬 + 우선순위 큐

링크 : https://www.acmicpc.net/problem/2461

풀이

• N개의 반이 있고, 각 반에는 M명의 학생이 있음.
• 각 학생마다 실력이 있고, 각 반에서 한 명씩 대표로 뽑아서 실력 차이를 최소로 하고 싶음.
• 즉, N명의 대표를 뽑을 때 최소 실력차가 가장 작은 집합을 만들고, 그 차이를 출력해야 함.

from queue import PriorityQueue

• Python 표준 라이브러리의 우선순위 큐 (최소 힙 역할) 사용

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

• N개의 반마다 M명의 학생 실력을 입력 받음
• A[i][j]는 i번째 반의 j번째 학생 실력

for i in range(N):
    A[i].sort()

• 각 반의 학생 실력을 정렬해서 가장 작은 수부터 선택할 수 있도록 함

pq = PriorityQueue()  # 최소 힙
pos = [0] * N          # 각 반의 현재 선택된 인덱스
max_val = 0

• pq: (값, 반 번호) 형태로 우선순위 큐에 저장
• max_val: 현재 선택된 값 중 가장 큰 값

for i in range(N):
    pq.put((A[i][0], i))         # 각 반에서 가장 작은 학생을 우선 삽입
    max_val = max(max_val, A[i][0])  # 초기 최대값 갱신

• 각 반에서 실력이 가장 낮은 학생부터 시작

while True:
    min_val, id = pq.get()     # 현재까지의 최솟값과 그 반의 번호
    answer = min(answer, max_val - min_val)  # 차이 최소 갱신

• 현재 pq에는 각 반에서 하나씩 뽑힌 학생들이 들어 있음
• 이 중 제일 실력이 낮은 학생을 꺼냄 → min_val
• 이 집합에서 최대 실력(max_val)과의 차이를 계산해서 answer 갱신

    pos[id] += 1
    if pos[id] >= M:
        break

• 해당 반의 다음 학생으로 이동
• 만약 그 반에서 더 이상 뽑을 수 없으면 반복 종료

    pq.put((A[id][pos[id]], id))
    max_val = max(max_val, A[id][pos[id]])

• 새로운 학생을 우선순위 큐에 추가
• 최대 실력 갱신

코드

# 백준 2461 - 대표 선수
# 분류 : 정렬 + 우선순위 큐

from queue import PriorityQueue

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

for i in range(N) :
    A[i].sort()

pq = PriorityQueue()
pos = [0] * N
max_val = 0
for i in range(N) :
    pq.put((A[i][0], i))
    max_val = max(max_val, A[i][0])

answer = 1e9
while True :
    min_val, id = pq.get()
    answer = min(answer, max_val - min_val)

    pos[id] += 1

    if pos[id] >= M :
        break

    pq.put((A[id][pos[id]], id))
    max_val = max(max_val, A[id][pos[id]])

print(answer)