Lv.3arraybinary-searchgreedyparametric-searchsorting
최소 간격 최대화
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
일직선 위에 집 N채가 있습니다. A[i]는 i번째 집의 좌표입니다. 좌표는 서로 다릅니다. 배열은 정렬되어 있지 않습니다.
이 중 K채를 골라 공유기를 설치하려 합니다. 간섭을 줄이기 위해 가장 가까운 두 공유기 사이의 거리를 최대로 만들고 싶습니다.
그 최댓값을 반환하세요.
입출력 예
| A | K | result |
|---|---|---|
[1, 2, 8, 4, 9] | 3 | 3 |
[1, 2, 3, 4] | 2 | 3 |
[5, 10] | 2 | 5 |
입출력 예 설명
예 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
- , 모든 좌표는 서로 다릅니다.
Expected complexity
- Time
- O(N log N)
- Space
- O(1)
Examples
| A | K | Expected |
|---|---|---|
[1,2,8,4,9] | 3 | 3 |
[1,2,3,4] | 2 | 3 |
[5,10] | 2 | 5 |
Hint
Hint
질문을 뒤집으세요. "최소 간격을 이상으로 유지하면서 채를 고를 수 있나?" 는 쉽게 판정됩니다. 정렬한 뒤 첫 집부터 시작해, 직전에 고른 집과 이상 떨어진 집을 만날 때마다 고르면 됩니다.
그리고 를 작게 할수록 조건이 느슨해져 더 많이 고를 수 있습니다. 즉 가능/불가능이 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 입니다(부등호 방향도 반대).
복잡도 목표
채를 고르는 모든 조합을 시도하면 경우의 수가 폭발합니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |