[JAVA][Baekjoon] 1300번 K번째 수 🌟🌟🌟🌟🌟

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

 

📌 접근 방식

처음엔 이걸 이진 탐색으로 풀 생각조차 하지 못했다.. 전혀 이 문제를 보고 이진 탐색을 떠올릴 수 없었다...

배열 B의 크기가 매우 커지기 때문에 이 배열을 직접 정렬하고 k번째 값을 찾는 방법으로 구현하면 시간 초과가 날 수 있다.
➡️ 이진 탐색을 활용하여 k번째 작은 값을 찾는 방법을 사용해야 함!

1. 배열 A의 원소 : A[i][j]=i×j 형태
2. 배열 B는 이 값을 오름차순으로 정렬한 배열
3. 주어진 k번째 작은 값을 구하는 과정에서, 값의 범위는 1부터 N^2까지이므로 이진 탐색을 사용하여 범위 내에서 k번째 원소를 찾을 수 있습니다.

이진 탐색을 적용한 방법:

• 배열 A에서 가능한 값의 범위는 1≤i×j≤N^2
• 중간값을 기준으로 그 값 이하인 원소의 개수를 세면 k번째 원소를 찾을 수 있음
• 각 값이 몇 번 등장하는지 카운팅하는 방법은 cnt+=min⁡(middle / i,N) N) ➡️ i번째 행에서 등장하는 값이 중간값 이하인 개수를 구하는 방식

[알고리즘] 이진 탐색(Binary Search)

 

✅ PASS CODE

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int start = 1;
        int end = K;
        int ans = 0;
        while(start <= end) {
            int middle = (start + end) / 2;
            int cnt = 0;
            for(int i=1; i<=N; i++) {
                cnt += Math.min(middle/i, N);
            }
            if(cnt < K) {
                start = middle + 1;
            } else {
                end = middle - 1;
                ans  = middle;
            }
        }
        System.out.println(ans);
    }
}

 

1️⃣ 이진 탐색:

• start와 end는 가능한 값의 범위를 설정. start는 1, end는 최대값 K로 시작함
• 각 중간값(middle)을 기준으로 배열 B에서 해당 값 이하인 원소의 개수를 센다.

2️⃣ 중간값 이하 원소 카운팅:

• cnt += Math.min(middle / i, N)로 각 행에서 middle 이하의 수의 개수를 더함

😊 느낀 점

이 문제는 처음에 어떻게 접근할지 정말 막막했다.. 😣 배열의 크기가 최대 N^2까지 커질 수 있기 때문에, 단순히 배열을 만들어서 정렬하면 시간초과가 날 것 같았다.. 그래서 이진 탐색을 이용해서 범위를 절반씩 좁혀가며 k번째 작은 값을 찾는 방법을 사용하게 되었다.

이진 탐색을 사용할 때, 각 중간값에 대해 A[i][j] 배열의 크기를 어떻게 세어야 할지도 많이 고민됐다.. 분명 하나하나 세는 방법이 아닌 중간 값을 이용해 효율적으로 계산할텐데,, 처음에는 감이 잘 안잡혔다. 처음에는 정말 헷갈리고 어려웠지만, 고민하며 손으로 먼저 풀어보다보니 해결할 수 있었다! 💪 다음에 다시 풀어봐야겠다 🤓