Binary Search on Answer 도입을 통한 최적 거리 탐색 시간 복잡도 O(N log MaxDistance) 달성

Context

최소 거리의 최댓값을 구하는 문제에서 모든 가능성을 탐색하는 Brute Force 방식의 비효율성 발생. 탐색 범위가 넓어질수록 O(N × MaxDistance)의 시간 복잡도로 인해 대규모 데이터셋 처리 시 성능 병목 지점 형성.

Technical Solution

• 결정 문제(Decision Problem)로의 변환을 통한 Binary Search on Answer 구조 설계
• 거리 값의 단조성(Monotonicity)을 활용하여 탐색 범위를 절반씩 축소하는 최적화 전략 채택
• 정렬된 좌표계를 기반으로 Greedy Placement 알고리즘을 적용한 가능 여부 판단 로직 구현
• '최소 거리 X가 가능하면 X-1도 가능함'이라는 논리적 전제로 불필요한 탐색 공간 제거
• O(N log N)의 정렬 과정과 O(N log MaxDistance)의 탐색 과정을 결합한 효율적 파이프라인 구성