Chocolate Distribution Problem
초콜릿 봉지가 몇 개 있고, packets[i]는 봉지 i에 들어 있는 초콜릿의 개수입니다. 학생 m명은 각각 정확히 한 봉지씩 받으므로, 서로 다른 봉지 m개가 나갑니다. 나눠 준 봉지 중 초콜릿이 가장 많은 봉지와 가장 적은 봉지의 차이가 가능한 한 작아지도록 봉지를 고르세요.
가능한 가장 작은 차이를 반환하는 minDifference라는 함수를 작성하세요.
함수
- packetsinteger-array
- 각 봉지에 들어 있는 초콜릿의 개수
- minteger
- 학생 수, 각 학생이 한 봉지씩 받음
- 반환값integer
- 나눠 준 패킷 중 가장 큰 것과 가장 작은 것의 차이를 가능한 한 최소화하기
제약 조건
2 ≤ m ≤ packets.length ≤ 1041 ≤ packets[i] ≤ 105- 두 봉지에는 같은 개수의 초콜릿이 들어 있을 수 있습니다.
예제
- 입력
- packets = [9, 3, 15, 7, 11, 4]m = 3
- 출력
- 4
- 설명
- 정렬하면 패킷은 3, 4, 7, 9, 11, 15입니다. 3, 4, 7과 7, 9, 11 모두 차이가
4이며, 이보다 더 가까운 세 개의 패킷은 없습니다.
- 입력
- packets = [20, 5, 18, 6, 19]m = 2
- 출력
- 1
- 설명
- 5와 6은 1만큼 차이가 나고, 18과 19, 19와 20도 마찬가지입니다. 같은 패킷은 없으므로 어떤 쌍도 1보다 더 작은 차이를 낼 수 없습니다.
- 입력
- packets = [8, 1, 5]m = 3
- 출력
- 7
- 설명
- 학생은 3명이고 꾸러미는 3개이므로 모든 꾸러미가 배부되고 차이는
8 - 1 = 7입니다.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
나눠 줄 가장 작은 패킷을 이미 알고 있다고 가정해 봅시다. 어떤 다른 패킷을 그것과 함께 나눠 줘야 할까요?
가장 작은 패킷을 고정하고, 크기순으로 바로 다음에 오는
m-1개의 패킷을 나눠 줍니다. 더 큰 패킷은 간격만 더 벌릴 뿐입니다. 정렬된 순서에서 이 패킷들은 서로 이웃해 있습니다.패킷을 정렬하세요. 이웃한
m개씩의 모든 구간은 마지막 패킷에서 첫 번째 패킷을 뺀 값이 차이인 윈도입니다. 윈도를 왼쪽에서 오른쪽으로 이동하면서 가장 작은 차이를 유지하세요.
풀이
모든 m개 패킷 그룹을 하나씩 시도하는 것은 너무 느립니다. 가장 좋은 선택은 패킷을 정렬했을 때 항상 서로 이웃한 m개 패킷입니다. 따라서 한 번 정렬한 다음, 한 번 순회하며 m개의 이웃한 패킷으로 이루어진 모든 구간의 차이 중 가장 작은 값을 구하면 됩니다.
가장 작은 패킷 수정
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
나눠 줄 가장 작은 봉투인 low를 정합니다. 가장 큰 봉투를 작게 유지하려면 low 이상인 봉투 중 가장 작은 m-1개를 고릅니다. 그러면 차이는 low 이상인 봉투 중 m번째로 작은 봉투에서 low를 뺀 값입니다. 모든 봉투를 low로 시도하고, 그 값 이상인 봉투가 m개보다 적으면 건너뛴 뒤, 가장 작은 차이를 유지합니다.
n개의 선택 각각에서 최대 n개의 봉투를 필터링하고 정렬합니다. 즉, O(n² log n)입니다. 크기가 서로 다른 봉투가 n = 10^4개라면 정렬만으로도 약 6 × 10^8번의 비교가 발생합니다.
알고리즘
- 정답이 넘을 수 없는 값으로
best를 시작합니다. - 각 묶음
low에 대해,low개 이상의 초콜릿이 들어 있는 모든 묶음을 모아 정렬합니다. - 그런 묶음이
m개 이상이면,m번째로 작은 값에서low를 뺀 값이 후보가 됩니다. - 가장 작은 후보를
best에 저장하고 반환합니다.
def minDifference(packets, m):
best = max(packets) - min(packets) # no gap can be wider than this
for low in packets:
# The packets that could go out alongside low, smallest first (low is one of them).
bigger = sorted(x for x in packets if x >= low)
if len(bigger) >= m:
best = min(best, bigger[m - 1] - low)
return bestm개의 패킷을 정렬하고 윈도우를 이동합니다
핵심 아이디어
정렬된 순서에서 윈도우 sizes[i..i+m-1]는 가장 작은 패킷이 처음에 있고 가장 큰 패킷이 마지막에 있으므로, 그 차이는 sizes[i+m-1] - sizes[i]입니다.
최선의 선택은 언제나 윈도우일 수 있습니다. 선택한 항목에서 가장 작은 항목과 가장 큰 항목 사이에 있는 패킷을 건너뛰었다면, 그 패킷을 가장 큰 항목과 바꾸세요. 가장 작은 항목은 그대로이고 가장 큰 항목은 더 작아질 수만 있으므로 차이는 커지지 않습니다. 빈틈이 없어질 때까지 반복하세요.
첫 번째 예제에서 크기가 3인 윈도우들의 차이는 4, 5, 4, 6이므로 정답은 4입니다. 정렬에는 O(n log n)의 비용이 들고, 윈도우를 이동하는 데는 O(n)이 듭니다.
알고리즘
- 패킷을 오름차순으로 정렬하여
sizes에 넣습니다. - 첫 번째 윈도우인
sizes[m-1] - sizes[0]으로best를 설정합니다. - 시작 위치
i를 1부터n-m까지 바꿔 가며sizes[i+m-1] - sizes[i]를best와 비교하고 더 작은 값을 유지합니다. best를 반환합니다.
def minDifference(packets, m):
sizes = sorted(packets)
best = sizes[m - 1] - sizes[0]
# The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
for i in range(1, len(sizes) - m + 1):
best = min(best, sizes[i + m - 1] - sizes[i])
return best
함정과 경계 사례
- 윈도우의 끝을
i+m-1대신i+m으로 설정하면 패킷m+1개를 측정하게 됩니다. - 윈도우를 하나 일찍 멈춥니다. 시작 인덱스는 0부터
n-m까지 포함합니다.m = 2일 때[1, 10, 20, 21]에서i < n-m조건으로 반복문을 실행하면 유일한 차이인 1을 놓칩니다. - 정렬을 건너뜁니다.
[9, 3, 15, 7, 11, 4]에서는 처음 세 패킷의 차이가 12이지만, 정답은 4입니다. - 첫 번째 윈도우만 측정합니다. 가장 작은 패킷
m개도 하나의 선택지이지만, 최선의 그룹은 어디서든 시작할 수 있습니다. - 숫자를 텍스트로 정렬합니다. JavaScript에서 비교 함수 없이
sort()를 사용하면100000이9보다 앞에 옵니다.
자주 묻는 질문3
초콜릿 분배 문제의 시간 복잡도는 얼마인가요?
정렬에는 O(n log n)이 걸리고 m개의 패킷으로 윈도우를 슬라이딩하는 데는 O(n)이 걸리므로, 전체 시간 복잡도는 O(n log n)입니다. 추가 공간은 정렬된 복사본을 만드는 경우 O(n)이고, 입력을 제자리에서 정렬하면 정렬 자체에 필요한 공간 외에는 O(1)입니다.
초콜릿 분배 문제는 슬라이딩 윈도우 문제인가요?
네, 정렬된 패킷에서 고정 크기 윈도우를 사용합니다. 누적 합 윈도우와 달리, 윈도우가 이동할 때 업데이트할 것이 없습니다. 각 윈도우의 차이는 마지막 패킷에서 첫 번째 패킷을 빼기만 하면 됩니다.
초콜릿 분배 문제를 정렬 없이 해결할 수 있을까요?
여기서 크기는 최대 10^5이므로 계수 정렬은 O(n + 10^5) 시간에 크기를 정렬하며, 같은 논리가 그대로 적용됩니다. 크기에 상한이 없다면 비교만으로는 O(n log n)보다 빠를 수 없습니다. m = 2일 때 두 패킷의 크기가 같을 경우에만 답이 0이고, 최악의 경우 중복을 찾아내려면 그만큼 비교해야 합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def minDifference(packets, m):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
packets = [9, 3, 15, 7, 11, 4] m = 3
예상 출력
4