a-066-k-closest-points-to-origin2026-07-18mediumleetcode #973neetcode150

원점에서 가장 가까운 K개의 점

#array#math#divide-and-conquer#geometry#sorting#heap-priority-queue#quickselect

↗ leetcode #973 · a-066-k-closest-points-to-origin

문제

· problem

P.a-066-k-closest-points-to-origin

원점에서 가장 가까운 K개의 점

X-Y 평면 위의 점들을 나타내는 배열 points가 주어졌을 때, points[i] = [xi, yi]이고 정수 k가 주어진다. 원점 (0, 0)에서 가장 가까운 k개의 점을 반환하시오. X-Y 평면 위의 두 점 사이의 거리는 유클리드 거리(√((x1 - x2)² + (y1 - y2)²))이다. 답은 어떤 순서로든 반환할 수 있다. 답은 순서를 제외하고는 유일하다고 보장된다.

제약

· 1 ≤ k ≤ points.length ≤ 10^4
· -10^4 ≤ xi, yi ≤ 10^4

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[[1,3],[-2,2]]
1

[[-2,2]]

example 2input → output

[[3,3],[5,-1],[-2,4]]
2

[[3,3],[-2,4]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
반환된 점들의 순서가 중요한가?
☐
거리 계산 시 제곱근을 구해야 하는가?
☐
여러 점이 동일한 거리에 있을 수 있는가?
☐
k가 배열 길이와 같으면 모든 점을 반환해야 하는가?
☐
음수 좌표도 거리 계산에 올바르게 처리되는가?
☐
원본 배열을 수정할 수 있는가?
☐
k = 0인 경우도 처리해야 하는가?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 힙 초기화

○

minHeap = []

○

minHeap = ()

○

minHeap = {x: y for x, y in points}

step 2· 각 점의 거리 계산│ 중첩

○

dist = (x ** 2) + (y ** 2)

○

dist = (x ** 2 + y ** 2) ** 0.5

○

dist = abs(x) + abs(y)

step 3· 거리-좌표 튜플을 힙에 추가│ 중첩

○

minHeap.append((dist, x, y))

○

minHeap.append((x, y, dist))

○

minHeap.append([dist, x, y])

step 4· 힙 구조 구성

○

heapq.heapify(minHeap)

○

minHeap = heapq.nsmallest(k, minHeap)

○

heapq.heappop(minHeap)

step 5· 결과 리스트 초기화

○

res = []

○

res = [None] * k

○

res = minHeap[:k]

step 6· K번 최소 요소 추출│ 중첩

○

_, x, y = heapq.heappop(minHeap)

○

dist, x, y = heapq.heappop(minHeap)

○

res.append(heapq.heappop(minHeap))

step 7· 결과 반환

○

return res

○

return res[:k]

○

return sorted(res)

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:

        minHeap = []

        for x, y in points:

            dist = (x ** 2) + (y ** 2)

            minHeap.append((dist, x, y))

        heapq.heapify(minHeap)

        res = []

        for _ in range(k):

            _, x, y = heapq.heappop(minHeap)

            res.append((x, y))

        return res

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[[1,3],[-2,2]]
1

→

[[-2,2]]

case 2

[[3,3],[5,-1],[-2,4]]
2

→

[[3,3],[-2,4]]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.