[BOJ] 1300. K번째 수 - Java

📝 문제

문제 | 백준 1300. K번째 수

💡 풀이 과정

⛓ 사용한 알고리즘: 이분탐색

우선 N의 최댓값이 $10^5$이기 때문에 $N^2$ 크기의 배열을 모두 채워서 K번째 수를 탐색하는 것은 시간 초과가 발생할 수 있다. 따라서 최대한 효율적으로 K번째 수를 골라내야 하는데, 문제에서 주어진 배열이 2차원 형태이기 때문에 일반적인 수열에서 K번째를 찾는 것을 적용하기는 쉽지 않다. 때문에 2차원 배열을 익숙한 수열의 형태로 바꾼 후, 그 안에서 효율적으로 K번째 수를 찾아내야 한다.

가장 먼저 한 것은 2차원 배열을 1차원 배열로 나타내보는 것이다. 이전에 다른 그래프탐색 문제에서 2차원 배열의 좌표를 int 형 정수로 나타내어 함수를 호출했던 것에서 아이디어를 얻었다. 그림으로 나타내보면 다음과 같다.

위와 같이 1차원 배열로 만든 후 K번째 수를 찾아내면 된다. 이 때 “K번째 수”라는 것은 “현재 B[K] 이하인 수가 총 K개 있다” 라고 해석할 수 있다. 예를 들어, 위 그림에서 K=2 이라면, 현재 수열에서 2(B[2]) 이하인 수가 총 2개 있음을 알 수 있다. 이는 행렬이 오름차순으로 정렬되어 있다는 성질을 갖고 있기 때문에 가능하다.

위의 성질을 바탕으로 생각해보면, 결과적으로 우리가 찾아야 하는 K번째 숫자를 $x$라고 했을 때, 이 $x$의 값을 조정해가며 $x$의 인덱스가 K와 일치하는 경우를 찾아내면 된다. 즉, $x$이하인 수가 K개라면, 해당 숫자는 “K번째 수”가 된다.

그렇다면 $x$이하인 숫자의 개수는 어떻게 구할 수 있을까? 2차원 배열의 각 행에서 $x$보다 작은 숫자는 $x$를 행 인덱스(1부터 시작)로 나눈 개수만큼 존재한다. 예를 들어 $x$=4인 경우를 살펴보면, $x$보다 작은 숫자의 개수는 다음과 같다.

정리해보면, 1~N까지의 수 중에서 임의로 $x$값을 가정하고 해당 값이 몇 번째 수인지 알아낸 후, 이에 따라 $x$값을 조정해가며 K번째 수를 찾아주면 된다. 이 때 $x$값을 더 효율적으로 찾기 위해 선형 탐색이 아닌 이분 탐색을 이용할 수 있다.

코드

import java.util.*;

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

        int N = sc.nextInt();
        int K = sc.nextInt();

        long l=1,r=K,ans=0;

        while(l<=r) {
            long mid = (l+r)/2;
            long cnt=0;

            for(int i=1;i<=N;i++) {
                cnt += Math.min(mid/i, N);
            }

            if(K<=cnt) {
                r = mid-1;
                ans = mid;
            } else {
                l = mid+1;
            }

        }

        System.out.println(ans);
    }
}