파이썬 알고리즘 311번 | [백준 2461번] 대표 선수 - two pointer + heap

311. 대표 선수

1) 어떤 전략(알고리즘)으로 해결?

two pointer + heap

2) 코딩 설명

• 여러 집단에서의 투 포인터
• 각 집단에서 뽑아온 것들 중 가장 작은 것들을 heap 에다가 넣어놓고, 이 heap에서 가장 작은 것을 빼고, 그 뺀 집단에서 하나 다시 충당하고, max 를 갱신하면서 while 문을 진행한다

<내 풀이>

import sys
import heapq

N,M = map(int,sys.stdin.readline().rstrip().split())
# M명으로 구성된 N개의 그룹에서 각각 하나 선발
# 이 선발된 아이들의 최솟값 - 최댓값 차이 최소 

max_value = 0
ability_list = []
compare_hq = [] 
group_idx = [1 for _ in range(N+1)] 
# 각 그룹의 인덱스 중 heap 에 들어갈 차례인 인덱스
# 각 그룹의 0 인덱스는 무조건 heap 에 들어가는 상황이므로 1로 초기화 

for i in range(N) : 
    ability = list(map(int,sys.stdin.readline().rstrip().split()))
    # 능력치 오름차순 정렬
    ability.sort()
    # 각 집단에서 능력치 가장 작은 아이들 선별
    # 이때 [최솟값 ... 최댓값] 으로 선별이 될텐데, 최댓값은 그대로 둔 채로 최솟값을 증가하며
    # 차이 최소화 하는 접근 방식
    max_value = max(max_value, ability[0]) # 최댓값은 고정된 값
    ability_list.append(ability)
    # i번째 그룹의 가장 작은 value 들로 heap에 채움 
    # (가장 작은 값, 그룹 번호)
    heapq.heappush(compare_hq, (ability_list[i][0], i)) 

answer = int(1e9) # 차이의 최솟값 (초기화는 무한대)
while compare_hq : 
    min_val, group_num = heapq.heappop(compare_hq) 
    answer = min(answer, max_value-min_val)
    # min_val 을 하나 더 증가시켜보면 어떨 지 검사
    if group_idx[group_num] == M : 
        break # 이미 이 group 에 해당하는 것들은 heap에 들어갔다가 나온 것이므로 검사 불가 
    heapq.heappush(compare_hq, (ability_list[group_num][group_idx[group_num]], group_num))
    max_value = max(max_value, ability_list[group_num][group_idx[group_num]])
    group_idx[group_num]+=1 # heap 에 들어갔으니, 인덱스 하나 증가 

print(answer)

<반성 점>

• 투포인터의 응용을 제대로 생각하지 못했습니다.

<배운 점>

• 투포인터와 힙의 결합이라는 새로운 접근법을 터득해서 좋습니다 ㅎㅎ 투포인터를 열심히 파야겠어요