[Python/파이썬] SW Expert Academy 20728번 공평한 분배 2

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AY6cg0MKeVkDFAXt&categoryId=AY6cg0MKeVkDFAXt&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

코드

for tc in range(1, int(input())+1):
    n, k = map(int, input().split())
    candy = list(map(int, input().split()))

    candy.sort()
    ans = int(1e9)
    for i in range(n-k+1):
        gap = candy[i+k-1]-candy[i]
        ans = min(ans, gap)
    print(f"#{tc} {ans}")

 

이 문제는 주어진 주머니를 사탕의 개수를 기준으로 정렬한 뒤, 슬라이딩 윈도우를 이용하여 풀 수 있다.

 

자세히 말하자면, 사탕의 개수를 기준으로 정렬하면 연속된 K개의 주머니들을 골랐을 때 사탕의 개수가 가장 많은 것과 가장 적은 것의 사탕 개수 차이를 최대한 줄일 수 있다. 그리고 이 중에서도 가장 작은 차이를 갖는 것이 무엇인지 알기 위해 슬라이딩 윈도우로 K개의 주머니 덩어리를 하나씩 살펴보며 각 덩어리의 사탕 개수 차이값 중 최소를 구하면 된다.

이때 각 덩어리의 사탕 개수 차이값은 K개로 묶은 범위의 첫번째와 마지막 주머니의 차이를 구하면 된다.