백준 1300번 K번째 수 (Java)

문제

백준 1300번 K번째 수 / 골드1
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 10⁵보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10⁹, N²)보다 작거나 같은 자연수이다.

풀이

문제의 접근을 어떻게 해야되는지 많은 고민을 하게 만든 문제이다. 문제는 2차원 배열의 값(인덱스의 곱)을 오름차순 1차원 배열로 만들었을 때, K번째 수인 B[k]를 구하는 문제이다. 이 문제를 해결하기 위해서는 B[k] = x라 가정 했을 때, 'x보다 작은 같은 원소의 개수는 k개'를 의미한다. 그렇기에 x를 기준으로 이분탐색을 진행하면서 k의 값을 찾아가면 수월하게 문제를 해결할 수 있다.

우선 이분탐색을 진행하기 위해 x의 start는 1로 end는 k로 지정한다. 이때, end를 k로 지정하는 이유는 이차원 배열을 일차원 배열로 변경 하면 x <= k 라는 사실을 확인 할 수 있다.

이후, 2차원 배열의 입장에서 보면 row 가 1일 경우, x보다 작은 수는 x/1개를 갖게 된고, row 가 n 일 경우는 x보다 작은 수는 x/n개를 갖게 된다. (단, x/n이 N을 넘지 않는 다는 사실을 유의해야 된다) 이러한 전제에 각 row의 합을 구하면 해당 수 mid가 몇 번째 인지 k를 알 수 있게 된다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int k = sc.nextInt();

        long start = 1;
        long end = k;
        while (start <= end) {
            long mid = (start + end) / 2;
            long cnt = 0;
            boolean over = false;
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(mid / i, N);
                if (cnt >= k) {
                    over = true;
                    break;
                }
            }

            if (over) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        System.out.println(start);
    }
}