Funcia
Lv.2binary-searchparametric-searchsortingtwo-pointers

K번째로 가까운 두 집

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

마을 큰길을 따라 집 NN채가 있고, i번째 집의 위치는 pos[i]입니다. 서로 다른 두 집으로 이루어진 쌍은 모두 N(N−1)/2N(N-1)/2개이고, 각 쌍의 거리는 두 위치의 차의 절댓값입니다.

모든 쌍의 거리를 작은 것부터 늘어놓았을 때 k번째 거리를 반환하세요. 거리가 같은 쌍도 각각 따로 셉니다. 같은 위치에 집이 여러 채 있을 수도 있습니다(거리 0).

입출력 예

poskresult
[1, 3, 1]10
[1, 6, 1]35
[9, 2, 5, 14]47

입출력 예 설명

예 1 — 거리는 |1-3| = 2, |1-1| = 0, |3-1| = 2이므로 가장 작은 거리는 0입니다.

예 2 — 거리는 0, 5, 5이므로 3번째는 5입니다.

예 3 — 정렬하면 위치는 2, 5, 9, 14, 거리는 3, 4, 5, 7, 9, 12이고 4번째는 7입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(pos: int[], k: long) → int

제한 사항

  • 2≤N=2 \le N = pos.length ≤50,000\le 50{,}000
  • 0≤0 \le pos[i] ≤106\le 10^6
  • 1≤1 \le k ≤N(N−1)/2\le N(N-1)/2 (32비트 정수 범위를 넘을 수 있습니다)

기대 복잡도

시간
O(N log N + N log V)
공간
O(1)

입출력 예

posk기대 출력
[1,3,1]10
[1,6,1]35
[9,2,5,14]47

힌트

힌트

쌍이 최대 약 12억 개이므로 모두 만들어 정렬할 수는 없습니다.

답 d를 이분 탐색하세요. 위치를 정렬해 두면 "거리가 d 이하인 쌍의 수"는 두 포인터로 O(N)O(N)에 셀 수 있습니다. 오른쪽 끝 r을 늘려 가며 pos[r] - pos[l] > d인 동안 l을 늘리면, r과 짝을 이루는 쌍이 r - l개입니다.

이 개수가 k 이상이 되는 가장 작은 d가 답입니다. 전체 O(Nlog⁡N+Nlog⁡V)O(N \log N + N \log V)입니다(VV는 위치의 범위).

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251020 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.