[BOJ] 2461번 - 대표 선수

[BOJ] 2461번 - 대표 선수

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

2461번: 대표 선수

문제 이해

---

문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제

 

 

알고리즘

---

문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제이다.

1. 접근 시에는 각 N개의 List를 Heapq로 구현 -> 맨 앞에 있는 값들을 매번 갱신하며 찾아보았지만, 시간 초과가 발생하였다.

조금 더 시간을 줄여보고자 하였으나, 아이디어가 생각이 안나 다른 분들의 알고리즘을 참고하여 보았다.

 

2. 방식은 모든 학생 값을 Heapq로 구현하고 반과 관련된 부분을 List로 별도로 나누어 구현하여 매번 N번씩 보는 것을 1번으로 줄여서 푸는 것을 알 수 있었다. 해당 방식을 참조하여 풀었더니 시간 내에 결과가 잘 출력이 되었다.

이해 하기 쉽게 말하면 결국 투포인터인데, Left는 매번 Heapq에서 Pop되는 값이며, Right 값은 현재 Max값과 Pop되어 있는 반에 대해서 후에 올값을 비교하여 더 큰값을 Right로 두고 푸는 것과 같다.

 

코드

---

#BOJ 2461번

import heapq
import sys

n , m = map(int,input().split())
check_list = [1]*(1001)
max_value = 0
all_number = []
datas = []
answer = sys.maxsize

for i in range(n) :
    temp = sorted(list(map(int,input().split())))
    max_value=max(temp[0],max_value)
    datas.append([])
    datas[i]=temp

    heapq.heappush(all_number,(temp[0],i))

while all_number :
    number , idx = heapq.heappop(all_number)
    min_value = number

    #print(number , max_value , min_value )
    answer = min(answer,max_value-min_value)
    if check_list[idx] == m :
        break
    heapq.heappush(all_number,(datas[idx][check_list[idx]],idx))
    max_value = max(max_value,datas[idx][check_list[idx]])
    check_list[idx]+=1

print(answer)