가장 가까운 드론 두 대의 거리 제곱

자바스크립트 코딩테스트 문제로 closest-pair-geometry 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard closest-pair-geometry 함수명: minimumSquaredDistanceBetweenDrones 제한 시간: 500ms

평면 위에서 서로 가장 가까운 드론 두 대의 거리 제곱을 구하세요.

문제 설명

각 드론의 위치가 [x, y] 형태로 담긴 배열 points가 주어집니다.

두 드론 a = [x1, y1], b = [x2, y2] 사이의 거리 제곱은 다음과 같습니다.

(x1 - x2)² + (y1 - y2)²

서로 다른 드론 두 대를 골랐을 때 가능한 거리 제곱의 최솟값을 반환하는 minimumSquaredDistanceBetweenDrones 함수를 작성하세요.

드론 두 대가 같은 좌표에 있을 수도 있으며, 이 경우 정답은 0입니다.

제한사항

2 <= points.length <= 200,000
각 원소는 [x, y] 형태입니다.
-10,000,000 <= x, y <= 10,000,000
좌표는 정수입니다.
서로 다른 드론이 같은 좌표에 있을 수 있습니다.
반환값은 JavaScript의 안전한 정수 범위 안에 들어옵니다.

예시

입력: [[0, 0], [3, 4], [7, 0]] -> 출력: 25
입력: [[1, 1], [1, 1], [10, 10]] -> 출력: 0
입력: [[-5, -5], [2, 3], [3, 2], [100, 100]] -> 출력: 2
입력: [[-4, 0], [-1, 10], [0, 0], [3, 10]] -> 출력: 16

힌트

모든 쌍을 비교하면 O(n²)이므로 입력 크기를 감당할 수 없습니다.
점들을 x좌표 기준으로 정렬하고 절반씩 나누어 생각해 보세요.
양쪽 절반의 정답을 구한 뒤에도, 가장 가까운 두 점이 분할선의 서로 다른 쪽에 있을 수 있습니다.
분할선 주변 후보를 y좌표 순서로 보면 현재 최솟값보다 멀어지는 후보를 빠르게 제외할 수 있습니다.

해설

점들을 x좌표 기준으로 정렬한 뒤 분할 정복을 적용합니다.

각 재귀 구간을 절반으로 나누어 왼쪽과 오른쪽 내부의 최소 거리 제곱을 각각 구하고, 둘 중 작은 값을 best로 둡니다. 하지만 전체 최근접 쌍이 분할선 양쪽에 하나씩 놓여 있을 수 있으므로 이 경우를 추가로 확인해야 합니다.

분할선의 x좌표를 midX라고 할 때 (point.x - midX)² < best인 점만 후보 띠에 넣습니다. 후보들을 y좌표 순서로 정렬한 뒤 각 점에서 다음 점들을 확인하되, y좌표 차이의 제곱이 best 이상이 되는 순간 이후 비교를 멈춥니다. 평면의 밀도 성질 때문에 이 띠 안에서 한 점이 실제로 비교할 후보 수는 상수 개로 제한됩니다.

작은 재귀 구간에서는 모든 쌍을 직접 비교할 수 있습니다. 구현할 때 각 재귀 결과를 y좌표 순서로 병합하면 매 단계마다 다시 정렬하지 않아 전체 시간 복잡도를 O(n log n)으로 유지할 수 있습니다.

거리 자체가 아닌 거리 제곱만 비교하므로 Math.sqrt가 필요 없고 부동소수점 오차도 피할 수 있습니다. 전체 시간 복잡도는 O(n log n), 추가 공간 복잡도는 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과