[BOJ][Java] 1300번 K번째 수

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1300

 

문제를 풀어서 보면 단순히 2차원 배열의 값들을 1차원 배열로 옮겨서 오름차순으로 정렬한 뒤

K번째 인덱스(1부터 시작)의 값을 출력하면 되는 문제다.

 

하지만 N의 값이 최대 10^5 이기 때문에 이를 2차원 배열 N*N으로 만든다면 최대 10^10 개의 값들이 생성된다.

따라서 단순히 2차원 배열의 값을 1차원 배열로 옮겨서 해결할 수는 없다.

 

따라서 다른 풀이를 생각해야 한다.

먼저 문제 조건에 따라 3 * 3 배열을 1차원 배열로 전환하고 오름차순 정렬하면

1 2 2 3 3 4 6 6 9가 되는 것을 알 수 있다.

이때 K번째 인덱스의 값은 절대 K값 이상이 될 수 없다는 것을 알 수 있다.

 

따라서 K번째 인덱스의 최댓값은 K, 최솟값은 1로 이진탐색을 활용하여 문제를 풀 수 있다.

 

 

이진탐색을 이용하여 풀 때 위의 방식처럼 특정 열에서 mid의 값보다 작은 값들의 개수를 카운트한 다음 만약

카운트한 값이 K보다 작다면 인덱스를 하나 높여서 다시 탐색하고 K보다 작거나 같은 경우 정답을 갱신하면서

이진탐색을 진행하면 된다.

 

package boj;

import java.util.*;

public class BOJ1300 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int ans = 0;
        int start = 1;
        int end = K;

        while(start <= end){
            int mid = (start + end) / 2;
            int cnt = 0;

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

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

        System.out.println(ans);
    }
}