[leetcode][719] Find K-th Smallest Pair Distance

문제 : https://leetcode.com/problems/find-k-th-smallest-pair-distance/

---

모든 요소들의 pair들의 최소 차 중 k 번째가 되는 수를 구하는 문제.

 

이진탐색으로 정답이 되는 범위를 줄여나가면서 찾는다.

여기서 low, high, mid는 단순히 nums 배열의 인덱스가 아닌 pair의 차이가 된다.

 

즉, low = 정답이 가능한 범위의 pair 최소 차이

high = 정답 범위의 pair 최대 차이  

mid = 범위를 줄이기 위해 몇 번째 최소 차인지 비교하기 위한 수. 가 된다.

 

nums를 오름차순으로 정렬한다.

low = 0, high = 최대값 - 최소값으로 세팅한다.

low를 nums를 한 번 탐색하면서 nums[i+1] - nums[i] 중 최소값으로 세팅해도 되지만 0보다 작은 값이 나올리가 없으므로 그냥 0으로 세팅했다.

mid = (high / low) / 2이다.

 

 

#1 mid가 pair들의 최소 차들중 몇번째인지 구한다.

여기에서는 투포인터를 사용했다.

왼쪽 포인터(left)는 nums배열의 앞에서부터 탐색하는데 사용되는 인덱스이다. 기준점. (0부터 차례로 증가)

오른쪽 포인터(right)는 nums[right] - nums[left]와 mid를 비교하는데 사용된다.

예를 들어, [1, 5, 7, 9] 가 있고 mid가 5인 경우

left = 0, right = 1 -> 5(right) - 1(left) = 4 < 5. (pair의 차이가 mid보다 작기 때문에 right를 증가시켜 다음 수도 mid보다 작은지 비교해야 한다.

left = 0, right = 2 -> 7(right) - 1(left) = 6 > 5. (pair 차이가 mid보다 크기 때문에 이후 차이들은 모두 mid 보다 클 것이다. -> 탐색 종료)

탐색이 종료되면 left를 pair로 하는 수들 중 mid(5) 보다 차이가 작거나 같은게 몇 개인지 구할 수 있다. (1개 = [{1,5}])

left를 1증가시켜 left가 1인 경우 mid보다 차이가 적게 나는 개수를 다시 구한다. 이 때, left는 1 증가하지만 right는 감소하거나 증가시키지 않는다. 왜냐하면 nums는 정렬되어 있기 때문에 right - left 에서 left가 증가하는 경우 right - left는 mid 보다 반드시 작을 것이기 때문이다. (우리가 구하고자 하는게 mid보다 작은 pair 차들의 수라는 것을 잊지말자.) 

 

nums를 모두 탐색했을 때 mid보다 작거나 같은 차들의 수를 구했을 때 이 수가 k보다 작은 경우 mid를 증가시켜야 한다. 따라서 low를 mid + 1로 갱신한다. (mid는 정답이 될 가능성이 없고 mid 보다는 큰 수가 정답이 될 수 있기 때문에)

k보다 같거나 클 경우 high를 mid로 갱신한다. (mid는 정답이 될 가능성이 있고 mid 보다 작은수도 정답이 될 가능성이 있기 때문에 mid를 포함하고 high를 갱신한다.)

mid가 k랑 같은 경우 이 수가 반드시 정답이 된다고 확신할 수 없는 이유는 mid는 값의 범위를 줄이기 위한 수에 불과하기 때문이다.

즉, mid 값과 같은 pair의 차이가 nums에 있다고 단정지을 수 없다.

 

#2 이를 low < high 인 경우 반복한다. low >= high가 됐을 때, low값이 정답이 된다.

 

시간 복잡도는 O(NlogM).

O(N) = #1 x O(logM) = #2

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/719.%20Find%20K-th%20Smallest%20Pair%20Distance.py

---

이진탐색은 괜찮은 문제가 많은 것 같다.

 

Today's Python

A // B : A/B 결과를 int로 받는다. int(A/B) 와 같은 결과. A/B는 결과를 float으로 반환한다.