[BOJ 1300] K번째 수 - 이분 탐색 (Java)

문제

https://www.acmicpc.net/problem/1300

1300번: K번째 수

 

풀이

이게 왜 정답률이 높은지 모르겠다. 

막상 풀면 쉬운데 접근법을 생각하기가 쉽지 않다. 

구글링을 통해 힌트를 얻어서 풀었다.

 

예제 설명

예제는 다음과 같다. 

N = 3, k = 7

3
7

3*3 배열에 각각 행과 열을 곱한 값이 입력되어 있다.

1	2	3
2	4	6
3	6	9

위 값들을 일렬로 쭉 나열 하면 아래와 같다.

1, 2, 3, 2, 4, 6, 3, 6, 9

 

오름 차순으로 정렬해보자.

1, 2, 2, 3, 3, 4, 6, 6, 9

 

여기서 7번째 수는 ? 6임을 알 수 있다.

 

하지만 주어진 값의 허용 범위에 따라, 위와 같은 방법으로는 100% 시간 초과가 발생한다. 

이걸 어떻게 이분탐색으로 풀 수 있을까? 

 

이분 탐색 적용

k 번째 수를 찾기 위해 최소 값과 최대 값을 정의한다.

이제 이분탐색을 하면서 k번째 수를 찾을 것이다.

int left = 1;

int right = k;

 

배열에서 mid 이하의 수가 k개 이상이라면 

right = mid -1;

배열에서 mid 이하의 수 k개 미만이라면 

left = mid +1;

 

이런식으로 이분 탐색을 진행하면, mid 이하의 수가 K개가 되었을 때 mid 값이 K번째 수가 된다.

 

그러면 배열에서 특정 수 이하의 숫자 개수를 어떻게 구할까?

각 원소의 값이 i*j 인 N*N 배열에서 아래와 같이 특정 수 이하의 숫자 개수를 행 별로 구할 수 있다.

Math.min (특정 수 / i ,  N) = i행의 특정 수 이하의 숫자 개수

만약 4 이하의 수의 개수를 구하면, 각 행별로 해당 값을 더하여 총 6개가 된다.

1	2	3	Math.min(4/1, 3) = 3
2	4	6	Math.min(4/2, 3) = 2
3	6	9	Math.min(4/3, 3) = 1

 

소스코드

package binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ1300 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long k = Long.parseLong(br.readLine());

        long left = 1;
        long right = k;
        long ans = 0;

        while(left <= right){
            long mid = (left+right)/2;

            // mid 보다 같거나 작은 수가 k 개 이상이라면?
            if(count(mid, N) >= k){
                ans = mid;
                right = mid - 1;
            } else {
                // mid 보다 같거나 작은 수가 K개 미만이라면?
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }

    public static int count(long mid, int N){
        // arr[i][j] = i * j 배열에서 mid 값보다 같거나 작은 숫자의 개수를 구한다.
        int cnt = 0;
        for(int i = 1; i <= N; i++){
            cnt += Math.min(mid/i, N);
        }
        return cnt;
    }
}