[Leetcode] 668. Kth Smallest Number in Multiplication Table

문제 : https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/

---

m x n 크기의 2차원 배열(1-indexed)이 있다. 배열 값은 각 요소들의 행, 열 인덱스의 곱이다.

m, n, k가 주어졌을 때, m x n 2차원 배열에서 k 번째로 작은 요소 값을 구해라.

---

k 번째로 작은 요소 값은 완탐을 하지 않는 이상 구하기 어렵기 때문에, 정수 x 보다 작은 요소 값들이 몇 개인지 구해보자.

 

m = 3, n = 3, k = 4을 예로 들어보자.

1	2	3
2	4	6
3	6	9

1

2

2

3

3

4

6

6

9

구하고자 하는 문제를 좀 더 분해해서 각 행에서 정수 x 보다 작은 요소 값들이 몇 개(let, cnt)인지를 먼저 구해보자.

각 요소 값들은 인덱스의 곱이란걸 사용하면 구할 수 있다. i 행은 i x 1, i x 2, i x 3, ... i x n. 의 요소들을 가진다.

1부터 n까지 1씩 증가하기 때문에 x보다 같거나 작은 가장 큰 값을 구하면 i 번째 행에서의 x보다 작은 요소 값들의 개수(let, tmpCnt) 를 알 수 있다.

이를 수식으로 나타내면 다음과 같다.

i x tmpCnt = x
tmpCnt = x / i (단, n보다 같거나 작아야 한다.)

즉, cnt는 x / i (소수점 버림)과 같고 i를 1 ~ m까지 모두 대입하여 구한 tmpCnt의 합이 우리가 구하고자 하는 cnt 가 된다.

위 예시에서 x 를 4라고 했을 때 각 행에서의 tmpCnt값들을 구해보면

i = 1 : 3 (4 / 1 = 4. 3(n)보단 같거나 작아야 하므로 3.)

i = 2 : 2 (4 / 2 = 2)

i = 3 : 0 (4 / 3/ = 0)

 

위에서 설명한 방법으로 x 값 이하의 값들을 가진 수들의 개수(let, cnt)를 알아낼 수 있을 때, 어떤 값이 정답이 될 수 있을까.

x가 2인 경우 cnt는 3이 되고 x가 3인 경우 cnt는 5가 된다.

실제 정답이 되는 경우는 3이다. 즉, x값 이하의 값들의 개수가 k보다 크거나 같은 경우의 x 값들중 가장 작은 값이 정답이 된다.

 

따라서 이진 탐색으로 x의 범위를 1 ~ nm 에서부터 줄여나가는데 cnt가 k보다 크거나 같은 경우, 정답을 x로 갱신하고 작은 값들을 찾아야 하므로 right를 x - 1로 세팅한다. 반대로 cnt가 k보다 작은 경우는 cnt가 k보다 크거나 같은 경우를 구해야 하므로 left를 x + 1로 갱신한다.

 

시간복잡도는 이진탐색하는데 드는 시간 O(log(MN))에 한 번 탐색에서 cnt를 구하는 O(M)을 합친 O(logNM * M).

 

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/668.%20Kth%20Smallest%20Number%20in%20Multiplication%20Table.cpp

---

참고 

https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/discuss/1580357/C%2B%2BPython-Clean-and-Simple-Solution-w-Detailed-Explanation-or-Binary-Search-with-Proof