BOJ 1300 - K번째 수

문제

N×N 배열 A에서 A[i][j] = i * j이다. 이 배열의 원소를 오름차순으로 정렬했을 때 K번째 수를 구하는 문제이다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 K가 주어진다. (1 ≤ K ≤ min(N², 2×10⁹))

출력

K번째 수를 출력한다.

예제

입력	출력
`3` `7`	`6`

풀이

이분 탐색으로 "값 m 이하인 원소의 개수가 K 이상이 되는 최솟값 m"을 구한다.

탐색 범위를 l = 1, r = K로 설정한다 (K번째 수는 K를 넘을 수 없음)
중앙값 m에 대해 배열에서 m 이하인 원소의 개수를 카운팅한다: i행에서 min(m / i, N)개의 원소가 m 이하
카운트가 K 미만이면 l = m + 1, 이상이면 r = m - 1로 범위를 좁힌다
이분 탐색이 종료되면 l이 K번째 수이다

핵심 아이디어: N×N 배열을 직접 만들지 않고, "m 이하 원소 개수"를 행별로 min(m/i, N) 합산하여 O(N)에 계산함으로써 매개 변수 탐색을 적용한다.

코드

package ASP_study.day299;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Day274BOJ1300K번째수이진탐색 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int K = Integer.parseInt(br.readLine());
		binary_search(N, K);
	}
 
	public static void binary_search(int n, int k) {
		int l = 1;
		int r = k;
		while (l <= r) {
			int m = (l + r) / 2;
			int count = 0;
			for (int i = 1; i <= n; i++) {
				count += Math.min(m / i, n);
			}
			if (count < k)
				l = m + 1;
			else
				r = m - 1;
		}
		System.out.println(l);
	}
}

복잡도

시간: O(N log X)
공간: O(N)

문제