문제 정의
좌표 배열 arr을 첫 번째 인수로, 숫자 num을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 원점 (0, 0)에서 가장 가까운 num개의 점을 찾아 배열로 반환해야 합니다.
여기서 평면 위 두 점 사이의 거리는 유클리드 거리(Euclidean distance)를 기준으로 계산합니다. 즉, 점 (x, y)와 원점 사이의 거리는 √(x² + y²) 공식으로 구할 수 있습니다.
입력 예시
const arr = [[3,3],[5,-1],[-2,4]]; const num = 2;
각 점과 원점 사이의 거리를 계산해 보면 다음과 같습니다.
- [3, 3] → √18 ≈ 4.24
- [5, -1] → √26 ≈ 5.10
- [-2, 4] → √20 ≈ 4.47
따라서 가장 가까운 2개의 점은 [3, 3]과 [-2, 4]이며, 기대하는 출력은 다음과 같습니다.
const output = [[3,3],[-2,4]];
해결 방법: 정렬 활용하기
가장 직관적인 접근 방식은 모든 점을 원점까지의 거리를 기준으로 오름차순 정렬한 뒤, 앞에서부터 num개만 잘라내어 반환하는 것입니다.
const arr = [[3,3],[5,-1],[-2,4]];
const num = 2;
const closestPoints = (arr = [], num = 1) => {
arr.sort(([a, b], [c, d]) => {
return Math.sqrt(a * a + b * b) - Math.sqrt(c * c + d * d);
});
return arr.slice(0, num);
};
console.log(closestPoints(arr, num));
코드 동작 원리
- 구조 분해 할당: sort 콜백 함수에서
[a, b],[c, d]형태로 각 점의 x, y 좌표를 바로 추출하여 코드를 간결하게 유지합니다. - 거리 계산:
Math.sqrt(a * a + b * b)로 각 점의 원점으로부터의 유클리드 거리를 구합니다. - 정렬 및 슬라이싱: 거리가 가까운 순으로 정렬한 후
slice(0, num)으로 앞의 num개 요소만 반환합니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[ [ 3, 3 ], [ -2, 4 ] ]
성능 개선 팁
정렬 방식의 시간 복잡도는 O(n log n)입니다. 데이터 양이 매우 많고 num이 작은 경우에는 힙(Heap) 자료구조를 활용하면 O(n log k)로, 부분 선택 알고리즘을 사용하면 평균 O(n)으로 최적화할 수 있습니다.
또한 단순히 거리를 비교하는 목적이라면 제곱근 연산(Math.sqrt)을 생략해도 됩니다. a² + b² 값 자체를 비교해도 크기 순서는 동일하게 유지되므로, 불필요한 연산 비용을 줄여 실행 속도를 높일 수 있습니다.