[backjoon] 2461번 대표선수 풀이(Python)

 

 

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

 

구간 내 모든반이 한명이상 포함되는 조건에서,능력치 최대-최소 차이를 구한다.

슬라이딩 윈도우의 정석같은 문제. 조건을 만족하는 연속된 구간중 최소 or 최댓값을 구하는문제.

 

풀이

left와 right 두 포인터로 구간을 설정한다.
이 구간(left ~ right) 안에 모든 반이 최소 한 명씩 포함되어 있다면, → left를 오른쪽으로 이동시키며 구간을 좁혀가고,그때마다 능력치의 차이(최댓값 - 최솟값)를 계산해 최솟값을 갱신한다.

반대로, 모든 반이 포함되지 않았다면 → right를 오른쪽으로 이동시켜 구간을 확장한다.

import sys
from collections import defaultdict

input = sys.stdin.readline

N, M = map(int, input().split())
students = []
for class_num in range(N):
    line = list(map(int, input().split()))
    for val in line:
        students.append((val, class_num))  # 능력치,반번호

# 능력치 기준으로 정렬
students.sort()

left = 0
min_diff = float("inf")
count = defaultdict(int)  # 반: 학생수
class_cnt_in_window = 0

for right in range(len(students)):
    ability, class_num = students[right]
    count[class_num] += 1
    if count[class_num] == 1:  # 처음 들어온 반
        class_cnt_in_window += 1  # 윈도우내 반의수+1

    # 모든 반이 포함된 경우
    while class_cnt_in_window == N:
        current_diff = students[right][0] - students[left][0]
        min_diff = min(min_diff, current_diff)

        # 왼쪽 포인터 이동
        count[students[left][1]] -= 1  # 반 학생수 제거
        if count[students[left][1]] == 0:  # 만약 그 반이 이제 존재하지않으면
            class_cnt_in_window -= 1  # 윈도우내 반의수-1
        left += 1
print(min_diff)