K Closest Points to Origin
평면에 n개의 점이 주어집니다. 점 i는 (xs[i], ys[i])입니다. 원점 (0, 0)에서 가장 가까운 k개의 점을 각각 쌍 [x, y] 형태로 반환하세요.
정답은 원점으로부터의 거리가 가까운 순서로 정렬하세요. 거리가 같으면 x가 더 작은 점을 먼저, 그다음 y가 더 작은 점을 먼저 배치하세요. 같은 점이 여러 번 나열되어 있으면 각 사본을 한 번씩 셉니다.
함수
- xsinteger-array
- x좌표 각 점의
- ysinteger-array
- 각 점의 y 좌표
- kinteger
- 반환할 점수는 몇 점인가요?
- 반환값integer-2d-array
- x, y 쌍으로 표시한 가장 가까운 k개의 점을 가까운 순서대로 반환하며, 거리가 같으면 x, 그다음 y를 기준으로 정렬합니다.
제약 조건
n == xs.length == ys.length1 ≤ k ≤ n ≤ 5000-104 ≤ xs[i], ys[i] ≤ 104- 항목은 반복될 수 있으며, 각 복사본은 별도의 항목입니다.
예제
- 입력
- xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
- 출력
- [[-1, 2], [2, -2]]
- 설명
- 제곱 거리는 10, 5, 8, 25입니다. 가장 작은 두 값은 순서대로 5인
(-1, 2)와 8인(2, -2)에 해당합니다.
- 입력
- xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
- 출력
- [[-1, 1], [1, -1], [1, 1]]
- 설명
(1, 1),(-1, 1),(1, -1)은 모두 거리의 제곱이 2이고,(0, 2)는 4입니다. 동률인 점들 중에서는(-1, 1)의 x값이 가장 작고,(1, -1)은 y값에 따라(1, 1)보다 앞에 옵니다.
- 입력
- xs = [7]ys = [-7]k = 1
- 출력
- [[7, -7]]
- 설명
- 점은 하나뿐이고 하나가 필요하므로, 답은 바로
(7, -7)입니다.
후속 질문
이제 점들이 한 번에 하나씩 도착하며, 점이 하나 도착할 때마다 지금까지의 점 중 가장 가까운 k개를 보고해야 합니다. 메모리가 얼마나 필요할까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
실제 거리가 필요한 경우는 없습니다.
√(x² + y²)대신 무엇을 비교해도 같은 순서를 얻을 수 있을까요?지금까지 본 점들 중 가장 가까운
k개를 유지한다고 해 봅시다. 새 점은 그중 어느 점과 경쟁할까요?k개 이하의 점을(x² + y², x, y)순서로 정렬된 최대 힙에 보관하세요. 새 점이 맨 위의 점보다 앞에 오면 맨 위의 점을 교체하고, 마지막에는 힙에서 점을 꺼내 답의 뒤에서부터 채우세요.
풀이
거리에는 제곱근이 필요하지 않습니다. x² + y²는 같은 순서를 제공하며 정수로 유지됩니다. n개 점 중 k개만 필요하므로, 지금까지 가장 가까운 점 k개를 담고 가장 먼 점이 맨 위에 있어 교체할 수 있는 최대 힙을 사용하면 전체 정렬 대신 O(n log k)의 비용이 듭니다.
가장 가까운 점을 k번 선택하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
답의 첫 번째 점은 모든 점 중 가장 가까운 점이고, 두 번째 점은 나머지 중 가장 가까운 점이며, 이런 식으로 이어집니다. 따라서 아직 선택되지 않은 점 중 (x² + y², x, y) 기준으로 가장 앞에 오는 점을 매번 선택하면서 k번 점들을 훑습니다.
한 번 훑을 때마다 n개의 점을 모두 확인합니다. n = 5000이고 k = 2500이면 이는 세 부분으로 이루어진 비교 1.25 × 10^7회입니다.
알고리즘
- 모든 점을 선택되지 않은 것으로 표시합니다.
k번 반복합니다. 선택되지 않은 점들을 살펴보고(x² + y², x, y)기준으로 가장 앞서는 점을 찾습니다.- 해당 점을 선택된 것으로 표시하고 답에
[x, y]를 추가합니다. - 답을 반환합니다.
def kClosest(xs, ys, k):
n = len(xs)
taken = [False] * n
result = []
for _ in range(k):
best = -1
for i in range(n):
# Compare (squared distance, x, y): the order the answer uses.
if not taken[i] and (best == -1 or
(xs[i] * xs[i] + ys[i] * ys[i], xs[i], ys[i]) <
(xs[best] * xs[best] + ys[best] * ys[best], xs[best], ys[best])):
best = i
taken[best] = True
result.append([xs[best], ys[best]])
return result모든 점 정렬
핵심 아이디어
정답은 전체 순서에서 처음 k개의 점이므로, 모든 점을 (x² + y², x, y)를 기준으로 정렬하고 처음 k개를 선택합니다. 예제 1에서 정렬된 키는 (5, -1, 2), (8, 2, -2), (10, 3, 1), (25, 0, 5)이며, 처음 두 개가 정답입니다.
k의 값과 관계없이 정렬에는 O(n log n)의 비용이 듭니다. k가 작으면, 이 작업의 대부분은 정답에 포함되지 않는 점들을 정렬하는 데 쓰입니다.
알고리즘
- 각 점의 키
(x² + y², x, y)를 구성합니다. - 키를 기준으로 점을 정렬합니다.
- 처음
k개의 점을[x, y]쌍으로 반환합니다.
def kClosest(xs, ys, k):
points = list(zip(xs, ys))
# Sort by squared distance, then x, then y: the order the answer uses.
points.sort(key=lambda p: (p[0] * p[0] + p[1] * p[1], p[0], p[1]))
return [[x, y] for x, y in points[:k]]최대 힙에서 가장 가까운 k개 유지하기
핵심 아이디어
지금까지 본 점 중 가장 좋은 k개를 유지합니다. 새 점은 유지 중인 점 가운데 순위가 가장 낮은 점만 밀어낼 수 있으므로, 유지 중인 점을 (x² + y², x, y) 기준의 최대 힙에 저장하고 해당 점이 맨 위에 오도록 합니다. k개의 점을 저장한 뒤에는 맨 위 점보다 순위가 앞서는 점이 그 점을 대체하고, 그 외의 점은 버립니다. 이미 저장된 k개의 점이 그 점보다 순위가 앞서기 때문입니다.
k = 3인 예제 2에서 처음 세 점을 처리한 뒤 맨 위에는 키가 (4, 0, 2)인 (0, 2)가 있습니다. (1, -1)의 키는 (2, 1, -1)이므로 순위가 앞서며, 이 점이 맨 위 점을 대체합니다.
힙은 부분적으로만 정렬되어 있으므로 맨 위 점을 k번 제거하고, 마지막 슬롯부터 첫 번째 슬롯까지 답을 채웁니다. 각 점의 힙 연산은 최대 O(log k)이므로 시간 복잡도는 O(n log k)이고 메모리 복잡도는 O(k)입니다.
알고리즘
(x² + y², x, y)를 키로 사용하는 빈 최대 힙을 만듭니다.- 처음
k개의 점을 각각 삽입합니다. - 이후 각 점을 맨 위의 점과 비교합니다. 순위가 더 높으면 교체한 뒤 아래로 내려가게 하고, 그렇지 않으면 건너뜁니다.
- 맨 위의 점을
k번 제거합니다. 제거한 각 점은 정답의 마지막 빈 위치를 채웁니다. - 정답을 반환합니다.
import heapq
def kClosest(xs, ys, k):
# heapq is a min-heap; negating every part of (distance, x, y) puts the
# farthest kept point, in the answer's order, on top.
heap = []
for x, y in zip(xs, ys):
item = (-(x * x + y * y), -x, -y)
if len(heap) < k:
heapq.heappush(heap, item)
elif item > heap[0]:
# The new point comes before the farthest kept one: swap them.
heapq.heapreplace(heap, item)
# Popping gives the farthest first, so fill the answer from the back.
result = [None] * len(heap)
for i in range(len(result) - 1, -1, -1):
_, x, y = heapq.heappop(heap)
result[i] = [-x, -y]
return result
함정과 경계 사례
- 동률 판정을 생략하는 경우. 예제 2에는 거리가 2인 점이 세 개 있습니다.
x를 비교한 다음y를 비교하지 않으면 입력 순서대로 나오며,(-1, 1),(1, -1),(1, 1)순서가 되지 않습니다. k개의 점을 최소 힙에 유지하는 경우. 힙의 최상단은 가장 가까운 점이므로, 점을 하나씩 제거할 때마다 정답에 필요한 점을 버리게 되고 결국 가장 먼 점k개가 남습니다.- 힙의 배열에서 답을 바로 읽는 경우. 배열은 일부만 정렬되어 있으므로, 먼저 점을 하나씩 제거하세요.
- 중복된 점을 제거하는 경우.
(5, 5)가 세 번 나열되어 있고k = 3이면, 정답은 그 점이 세 번 나오는 것입니다.
자주 묻는 질문4
원점에서 가장 가까운 K개 점의 시간 복잡도는 얼마인가요?
모든 점을 정렬하는 데는 O(n log n)이 걸립니다. 힙 버전은 스캔에 O(n log k), 살아남은 k개를 정렬하는 데 O(k log k)이 걸리며, 메모리에는 O(k)개의 점만 유지합니다.
k개의 가장 가까운 점을 구할 때 최소 힙이 아니라 최대 힙을 사용하는 이유는 무엇인가요?
새로운 점은 유지 중인 k개의 점 중 가장 멀리 있는 점과 경쟁하므로, 그 점이 맨 위에 있어야 합니다. 최소 힙은 n개의 점을 모두 저장해야 가장 가까운 k개를 제거할 수 있으며, 이 경우 O(k) 대신 O(n)의 메모리가 필요합니다.
거리를 비교하려면 제곱근이 필요한가요?
아니요. 음수가 아닌 수의 경우, a < b인 것과 √a < √b인 것은 정확히 같은 조건이므로, x² + y²는 거리와 동일한 순서를 제공합니다. 또한 정수로 유지됩니다. 여기서는 최대 2 × 10^8이므로 32비트 범위 안에 있습니다.
원점에서 가장 가까운 K개의 점을 O(n) 시간에 구할 수 있나요?
평균적으로는 그렇습니다. Quickselect는 같은 (x² + y², x, y) 순서에 따라 임의의 피벗을 기준으로 점들을 분할하고, 평균 O(n) 시간에 위치 k를 포함하는 쪽에서만 계속 진행합니다. 해당 위치의 왼쪽에 있는 k개의 점이 답이며, 이 점들을 정렬하면 O(k log k)가 추가됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def kClosest(xs, ys, k):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
xs = [3, -1, 2, 0] ys = [1, 2, -2, 5] k = 2
예상 출력
[[-1, 2], [2, -2]]