[ 백준 ] 1300번 K번째 수 (Java 자바)

🔗 문제 링크: 백준 1300번 - K번째 수

 

문제 설명

 

이 문제는  N * N  크기의 2차원 배열  A 에서 K번째로 작은 수를 구하는 문제이다.

배열  A 는  A[i][j] = i * j 로 구성되어 있다. 실제 배열 전체를 생성하거나 정렬할 필요 없이,

파라메트릭 서치(Parametric Search)를 이용하여 후보 값  mid 에 대해 배열에서  mid  이하의 숫자가 몇 개 있는지를 세어 K번째 수를 찾는다.

 

입력 조건

• 첫 줄: 배열의 크기  N 과  k  (K번째 수)

• N 은 배열의 행/열 개수,  k 는 정렬했을 때의 순서를 의미한다.

---

풀이 과정

📌 문제 요약

• 목표:

 A[i][j] = i * j 로 구성된  N * N  배열에서 K번째로 작은 수를 구한다.

• 특징:

실제 배열을 생성하거나 정렬하지 않고, 특정 후보 값  mid 에 대해 배열 내에서  mid  이하의 숫자가 몇 개인지를 계산하는 방식으로 문제를 해결한다.

 

📌 해결 전략

1. 이분 탐색(Parametric Search) 적용:

• 탐색 범위 설정:

• left: 배열에서 가능한 최소값은 1 ( A[1][1] )

• right: 2차원 배열에서 K번째 수는  k 를 넘지 않으므로  k 로 설정

• 후보 판별:

임의의 후보 값  mid 에 대해 배열에서  mid  이하의 숫자가 몇 개인지 계산한다.

 

2. 숫자 개수 세기:

각 행  i 에 대해, 한 행에서  mid  이하의 숫자 개수는

Math.min(N, mid / i);

 로 구할 수 있다.

(한 행에는 최대  N 개의 숫자만 존재하기 때문에  mid / i 가  N 을 초과하지 않도록 한다.)

모든 행에 대해 이 값을 합산하여  mid  이하의 숫자가 총 몇 개인지를 구한다.

 

3. 이분 탐색 진행:

• 만약 구한 개수가  k  이상이면, 현재  mid  값은 K번째 수의 후보가 될 수 있으므로 결과를 갱신하고,

더 작은 값에서도 가능한지 확인하기 위해 오른쪽 범위를 줄인다.

• 반대로 구한 개수가  k 보다 작으면,  mid 가 너무 작다는 의미이므로 왼쪽 범위를 늘려서 탐색을 진행한다.

 

📌 실제 배열을 만들거나 정렬하지 않고, K번째 수의 후보를 찾는 방법

배열 A는 A[i][j] = i * j로 구성되어 있으며, 각 행은 오름차순으로 정렬되어 있다.

따라서, 임의의 후보 값 mid에 대해 배열에서 mid 이하의 숫자가 몇 개 있는지를 셀 수 있다.

 

구체적인 방법은 다음과 같다.

1. 각 행 i의 원소는 i, 2_i, 3_i, ..., N_i로 구성되어 있다.

이 행에서 mid 이하의 숫자의 개수는 mid / i로 구할 수 있다.

단, 한 행에는 최대 N개의 원소밖에 없으므로, 실제 개수는 min(N, mid / i)이다.

2. 모든 행에 대해 위의 값을 합산하면, 배열 A에서 mid 이하의 숫자가 총 몇 개 있는지 알 수 있다.

3. 이 값을 k와 비교하여,

• 만약 count >= k라면, 후보 mid는 K번째 수보다 크거나 같다는 의미이므로,

mid를 K번째 수의 후보로 보고 더 작은 값에서도 가능한지 탐색한다.

• count < k라면, 후보 mid가 너무 작다는 의미이므로 mid를 늘려 탐색한다.

 

이렇게 이분 탐색을 통해 범위를 좁혀가며 최종적으로 K번째 수에 해당하는 최소 mid를 찾게 된다.

이 방법은 실제 배열을 구성하지 않아도 각 행의 특성을 이용해 mid 이하의 원소 개수를 빠르게 계산할 수 있기 때문에 효율적이다.

 

📌 시간 복잡도 분석

• 이분 탐색은  O(log k) 번 반복하며, 각 반복마다  N 번의 연산을 수행하므로,

전체 시간 복잡도는  O(N log k) 이다.

 

package BinarySearch;

import java.util.Scanner;

/*
    BOJ Gold 1, K번째 수
    https://www.acmicpc.net/problem/1300
    파라메트릭 서치를 이용하여 K번째 수를 찾는 문제
    
    배열 A는 A[i][j] = i * j로 구성되어 있다.
    실제 배열을 생성하거나 정렬하지 않고, 
    특정 값(mid) 이하의 숫자가 몇 개인지 계산해 K번째 수의 후보를 찾아내는 방식으로 해결한다.
 */

public class BOJ_G1_1300 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   // 배열의 크기 (N x N)
        int k = sc.nextInt();   // 찾고자 하는 K번째 수

        int left = 1;           // 가능한 최소값 (A[1][1])
        int right = k;          // K번째 수는 k를 넘지 않으므로 최대값을 k로 설정
        int answer = 0;

        // 이분 탐색으로 K번째 수를 찾는다.
        while (left <= right) {
            int mid = (left + right) / 2;  // 후보 값
            int count = 0;                 // mid 이하의 숫자가 몇 개인지 카운트

            // 각 행에서 mid 이하의 숫자 개수를 계산
            for (int i = 1; i <= N; i++) {
                // 한 행에는 최대 N개의 숫자밖에 없으므로, mid / i가 N을 초과하지 않도록 처리한다.
                count += Math.min(N, mid / i);
            }

            // count가 k 이상이면, mid 값이 K번째 수의 후보가 될 수 있다.
            if (count >= k) {
                answer = mid;     // 후보 값 갱신
                right = mid - 1;  // 더 작은 값에서도 가능한지 확인한다.
            } else {
                left = mid + 1;   // mid가 너무 작으므로 범위를 확장한다.
            }
        }
        System.out.println(answer);
    }
}