[ 2461 ] [ Two-Pointer ] 대표 선수

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

2461번: 대표 선수

---

풀이 과정

---

• 처음엔 그냥 무식하게 탐색으로 하려고 했으나 계속 시간초과가 나옴.

  • 생각해보니 최대 1000개 학급에 최대 1000명의 학생이 가능한데 조건을 걸더라도 1000의 1000제곱은 풀릴리가 없음,,

• 고민하다 찾아보니 투포인터 알고리즘을 사용한다고 해서 투포인터 알고리즘으로 풀이

  • 모든 각각의 학급 내 학생들을 오름차순으로 정렬한 후, 초기에는 각 학급에서 능력치가 가장 낮은 학생들만 뽑아서 그룹을 만든다.
  • 차이를 좁히기 위해서는 최솟값을 올리던지 최댓값을 내리던지 해야 하는데.. 능력치가 낮은 학생에서 높은 학생 순으로 진행하므로 최댓값을 내릴수 없으므로 최솟값을 올리는 방식만 고려하면 된다.
  • 최소 히프를 사용해서 능력치가 가장 낮은 학생을 뽑고, 그 학생이 속한 그룹의 다음 학생을 다시 히프에 넣어주는 방식으로 진행
  • 과정 중에 하나의 반의 마지막 학생이 최솟값인 경우 더이상 최솟값을 갱신할 수 없으므로 종료하면 된다.
  • 과정 중 최댓값과 최솟값의 차이는 계속해서 갱신해준다.

---

소스 코드

---

import sys
import heapq
from collections import deque

input = lambda : sys.stdin.readline().rstrip()

n, m = map(int, input().split())
students = [deque(sorted(list(map(int, input().split())))) for _ in range(n)]

heap = []

min_value = int(10e9)
max_value = 0

for i in range(len(students)):
    v = students[i].popleft()
    max_value = max(max_value, v)
    min_value = min(min_value, v)
    heapq.heappush(heap, [v, i])

sumation = max_value - min_value

while heap:
    prev_min_value, pos = heapq.heappop(heap)
    if not students[pos]:
        # 해당 deque가 비어있다면 더이상 갱신 불가능
        break

    new_value = students[pos].popleft()
    heapq.heappush(heap, [new_value, pos])

    if max_value < new_value:
        max_value = new_value
    min_value = heap[0][0]
    sumation = min(sumation, max_value - min_value)


print(sumation)