Funcia
Lv.3arraybinary-searchgreedyparametric-searchsorting

최소 간격 최대화

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

일직선 위에 집 N채가 있습니다. A[i]는 i번째 집의 좌표입니다. 좌표는 서로 다릅니다. 배열은 정렬되어 있지 않습니다.

이 중 K채를 골라 공유기를 설치하려 합니다. 간섭을 줄이기 위해 가장 가까운 두 공유기 사이의 거리를 최대로 만들고 싶습니다.

그 최댓값을 반환하세요.

입출력 예

AKresult
[1, 2, 8, 4, 9]33
[1, 2, 3, 4]23
[5, 10]25

입출력 예 설명

예 1 — 정렬하면 [1, 2, 4, 8, 9]입니다. 1, 4, 8을 고르면 간격이 3과 4라 최소 간격이 3입니다. 어떻게 골라도 3보다 크게 할 수는 없습니다.

예 2 — 2채만 고르니 양 끝 1과 4를 골라 거리 3이 최대입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

Function signature

solution(A: int[], K: int) → int

Constraints

  • 2≤N≤200,0002 \le N \le 200{,}000
  • 2≤K≤N2 \le K \le N
  • 0≤A[i]≤1090 \le A[i] \le 10^9, 모든 좌표는 서로 다릅니다.

Expected complexity

Time
O(N log N)
Space
O(1)

Examples

AKExpected
[1,2,8,4,9]33
[1,2,3,4]23
[5,10]25

Hint

Hint

질문을 뒤집으세요. "최소 간격을 XX 이상으로 유지하면서 KK채를 고를 수 있나?" 는 쉽게 판정됩니다. 정렬한 뒤 첫 집부터 시작해, 직전에 고른 집과 XX 이상 떨어진 집을 만날 때마다 고르면 됩니다.

그리고 XX를 작게 할수록 조건이 느슨해져 더 많이 고를 수 있습니다. 즉 가능/불가능이 T → F 순서로 바뀌므로, 이분탐색 방향이 반대입니다.

while (lo < hi) {
    mid = lo + (hi - lo + 1) / 2;   // 올림!
    if (Check(mid)) lo = mid;       // 가능 → 더 크게
    else hi = mid - 1;
}

+1 올림을 빠뜨리면 lo와 hi가 인접할 때 mid == lo가 되어 무한루프가 납니다. 그리고 판정 조건은 개수 >= K 입니다(부등호 방향도 반대).

복잡도 목표

KK채를 고르는 모든 조합을 시도하면 경우의 수가 폭발합니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.