Funcia
Lv.3arraybinary-searchgreedyparametric-searchsorting

최소 간격 최대화

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
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이 최대입니다.

효율성

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

함수 시그니처

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

제한 사항

  • 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, 모든 좌표는 서로 다릅니다.

기대 복잡도

시간
O(N log N)
공간
O(1)

입출력 예

AK기대 출력
[1,2,8,4,9]33
[1,2,3,4]23
[5,10]25

힌트

힌트

질문을 뒤집으세요. "최소 간격을 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채를 고르는 모든 조합을 시도하면 경우의 수가 폭발합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251400 ms추정
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1000 ms도출됨

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.