백준 1300 k번째 수 찾기

문제

풀이

import java.util.*;

public class Q1300_k번째수 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long result = 0;

        int s = 1;
        int e = k;
        // 정답1
        while (s <= e) {
            int mid = (s + e) / 2;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                cnt += Math.min(mid/i, n);
            }
            if (cnt < k) {
                s = mid + 1;
            }else {
                e = mid - 1;
                result = mid;
            }
        }
        
        // 정답2
        while (true) {
            int mid = (s + e) / 2;
            int cnt = 0;
            for (int i = 1; i <= n; i++) {
                cnt += Math.min(mid/i, n);
            }
            if (cnt < k) {
                s = mid + 1;
                
            }else {
                e = mid - 1;
            }
            if (s > e) {
                System.out.println(s);
                break;
            }
        }
        System.out.println(result);
    }
}

리뷰

오름차순으로 배열을 정렬했을 때 B[k]를 찾으라는 것을 통해 이진탐색을 적용해야하는 것을 알 수 있다.

그런데 이진탐색을 여기에 어떻게 적용해야 하는지가 문제다ㅜ

여기서 2차원 배열은 n행이 n행으로 구성되어 있다.

위와 같은 배열에서 k번째 수는 k를 넘지 않는다.
예시로 주워진 k=7일때 위의 배열을 오름차순 정렬을 한다고 하면 arr[7] = 6으로 k = 7보다 작은것을 알 수 있다. 또한 6보다 작은 값의 개수는 위의 배열에서 총 k-1개인 6개가 된다.

1. 따라서 k번째 수를 찾기 위해서는 k보다 작거나 같은 수를 찾아야 하기 때문에
   시작 인덱스 s = 1
   끝 인덱스 e = k로 설정한다.

2. 시작 인덱스가 끝 인덱스보다 작거나 같을때까지 탐색을 수행할때

   • 중앙값보다 작은 수의 개수가 k보다 작으면(cnt < k)
     s = 중앙값 + 1
   • 중앙값보다 작은 수의 개수가 k보다 크거나 같다면(cnt >= k)
     e = 중앙값 - 1
     result = 중앙값
     으로 갱신을 해준다.

3. 결국 작은 수의 개수가 k-1개인 중앙값이 우리가 구하는 답이 된다.

   • k = 7일 때 그 값은 6이 되고,
     중앙값이 6일 때, 6보다 작은 수의 개수는 6개(k - 1)이므로
     중앙값 6이 답이 된다.

이진탐색을 풀어보았을 때 반복문을 빠져나왔을때(s와e가 교차했을 때)
s는 조건을 만족하는 최소값
e는 조건을 만족하지 않는 최대값을 가지고 있었다.

내가 풀었던 풀이방법이랑 달라 이해하는데 오래 걸렸다ㅜ