문제 소개
곱셈표(Multiplication Table)를 떠올려 본 적이 있을 것입니다. 그렇다면 이 곱셈표 안에서 k번째로 작은 수를 빠르게 찾아낼 수 있을까요? 문제는 다음과 같습니다. 세로 길이가 m이고 가로 길이가 n인 m × n 크기의 곱셈표와 양의 정수 k가 주어졌을 때, 표에 있는 수들 중 k번째로 작은 값을 구하는 것입니다.
예시
m = 3, n = 3이고 k = 6이라고 가정해 보겠습니다. 이때 출력 결과는 4가 됩니다. 곱셈표는 다음과 같이 만들어지기 때문입니다.
| 1 | 2 | 3 | |
| 1 | 1 | 2 | 3 |
| 2 | 2 | 4 | 6 |
| 3 | 3 | 6 | 9 |
표의 모든 원소를 오름차순으로 정렬하면 [1, 2, 2, 3, 3, 4, 6, 6, 9]가 되고, 여기서 6번째 값은 4입니다.
해결 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "어떤 값 x 이하인 수가 곱셈표에 몇 개 존재하는가?"를 세는 함수를 만들고, 이 개수가 k 이상이 되는 최솟값 x를 찾는 것입니다.
1단계: 개수 세기 함수 ok() 정의
- ok(m, n, x) 함수는 m, n, x를 매개변수로 받습니다.
- ret := 0 으로 초기화합니다.
- i := 1부터 n까지 반복하면서 다음을 수행합니다.
- temp := min(x / i, m) — i번째 행에서 x 이하인 수의 개수입니다.
- ret := ret + temp — 각 행의 개수를 누적합니다.
- 최종 ret(즉, x 이하인 수의 총개수)을 반환합니다.
2단계: 이진 탐색으로 정답 찾기
- ret := -1, low := 1, high := m * n 으로 초기화합니다.
- low <= high인 동안 반복합니다.
- mid := low + (high - low) / 2
- cnt := ok(m, n, mid) — mid 이하인 수의 개수를 계산합니다.
- 만약 cnt >= k라면:
- high := mid - 1 (더 작은 범위 탐색)
- ret := mid (후보 저장)
- 그렇지 않으면:
- low := mid + 1 (더 큰 범위 탐색)
- 반복이 끝나면 ret을 반환합니다.
이 방식의 시간 복잡도는 O(n log(m×n))으로, 곱셈표 전체를 생성하지 않고도 정답을 구할 수 있다는 점이 큰 장점입니다.
C++ 구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int ok(int m, int n, int x){
int ret = 0;
for(int i = 1; i <= n; i++){
int temp = min(x / i, m);
ret += temp;
}
return ret;
}
int findKthNumber(int m, int n, int k) {
int ret = -1;
int low = 1;
int high = m * n ;
while(low <= high){
int mid = low + (high - low)/ 2;
int cnt = ok(m, n, mid);
if(cnt >= k){
high = mid - 1;
ret = mid;
}else low = mid + 1;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findKthNumber(3,3,6));
}입력
m = 3, n = 3, k = 6
출력
4
마무리
곱셈표에서 k번째로 작은 수를 찾는 문제는 단순히 표를 만들어 정렬하는 O(mn log(mn)) 방식보다, 이진 탐색과 행별 개수 계산을 결합한 위 알고리즘이 훨씬 효율적입니다. 특히 m과 n이 클 때 그 차이가 두드러지므로, 코딩 테스트나 알고리즘 학습에서 꼭 익혀두면 좋은 패턴입니다.