[백준] 2461번 : 대표 선수 Python

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

2461번: 대표 선수

 

입력 받은 각각 학급별 선수들을 오름차순으로 정렬하였다. 
그리고 pointer 처럼 각각의 0번째 인덱스 값들을 찍어서 비교한다 

12	16	43	67
7	17	48	68
14	15	54	77

이 경우 max_value - min_value 값은 14 - 7 = 7 이 된다. 
오름차순 정렬에서 , 최댓값과 최솟값의 차이를 줄이기 위해서는 min_value 값을 크게 만들어주기 위해 7값이 있는 array[1]의 인덱스를 오른쪽으로 한칸 이동시킨다. 

12	16	43	67
7	17	48	68
14	15	54	77

한칸 이동한 경우, max_value - min_value = 17-14 = 3 이다. 결과값을 7에서 3으로 갱신해준다. 

이런 알고리즘을 반복하여 가장 오른쪽으로 많이 전진한 index가 m-1까지 도달하면 종료시킨다 

이걸 그대로 구현한 첫번째 코드는 시간초과가 발생했다.. for문에서 O(n)이 발생해서 그런것 같다 

n, m = map(int, input().split())
array = []
answer = int(1e9) # 차이가 최소
for i in range(n):
    data = list(map(int, input().split()))
    data.sort()
    array.append(data)

pointers = [0] * n
while True:
    if max(pointers) >= m:
        break
    max_value = 0
    min_value = int(1e9)
    min_pointer = 0 # index
    for i in range(n):
        if min_value > array[i][pointers[i]]:
            min_value = array[i][pointers[i]]
            min_pointer = i
        if max_value <= array[i][pointers[i]]:
            max_value = array[i][pointers[i]]

    answer = min(answer, max_value-min_value)
    pointers[min_pointer] += 1

print(answer)

 

그리하여 다른 블로그를 참고하여 heapq (우선순위 큐) 자료형을 쓰는 방법을 알아내여 적용했다. 원리는 똑같은데 다른점은 heapq가 tree의 root값이 가장 작은 값인데, 이를 heappop하면 현재 n 개 반의 대표중 능력치가 최솟값인 선수 정보를 바로 얻을 수 있다는 것이다. 

 

import heapq

n, m = map(int, input().split())
array = []
answer = int(1e9) # 차이가 최소
queue = [] # heapq 는 가장 작은 요소를 뱉어냄
max_value = 0 # ex) 14
for i in range(n):
    data = list(map(int, input().split()))
    data.sort()
    array.append(data)
    max_value = max(max_value, data[0])
    heapq.heappush(queue, (data[0],i)) # data 중에 가장 작은 값 ex) 12, 7, 14를 넣기 위함
pointer = [0] * (n+1) # n 개 클래스가 지금 가리키는 각각의 인덱스

while queue:
    x = heapq.heappop(queue) # ex) 7
    min_value = x[0]
    index = x[1] # 속한 그룹
    answer = min(max_value - min_value, answer) # 14-7 = 7
    if pointer[index] == m-1:
        break # array에서 값 꺼낼 때 index 초과 문제 방지
    pointer[index] += 1
    heapq.heappush(queue, (array[index][pointer[index]],index))
    max_value = max(max_value, array[index][pointer[index]])

print(answer)