[백준 JAVA] 1300 : K번째 수

[백준 1300] K번째 수 : https://www.acmicpc.net/problem/1300

---

문제 조건 정리

 

1. 크기가 N×N인 배열 A 
2. A[i][j] = i×j
3. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N
4. B를 오름차순 정렬했을 때, B[k]를 구해보자.
5. 배열 A와 B의 인덱스는 1부터 시작

---

입력

 

1. 첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다.
2. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

 

---

문제를 풀기 전

 

1. 배열을 만드는 게 아니라 다른 방법을 사용해야할 것이라고 생각함.
2. k번째 수는 k를 넘어설 수 없는 것을 확인
3. k번째 수는 1~k 중 하나 -> 이분탐색
4. 이분탐색의 mid를 기준으로 A배열을 검사
5. A배열에서 mid이하인 수의 개수를 세는 방법? -> 각 행(i)마다 (n*i / i) = n 
   행에서 가장 큰 요소가 mid보다 작을 수도 -> 각 행(i)마다 min((mid / i), n)
6. mid를 구성하는 start와 end가 같아지는 순간에 mid를 정답으로 반환

---

코드

 

package baekJoon;

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

public class BJ1300 {

    static int n;
    static int k;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());
        k = Integer.parseInt(bufferedReader.readLine());

        System.out.println(binarySearch(1, k));

    }

    private static long binarySearch(long start, long end) {
        long mid = 0;
        long count = 0;

        while (start <= end) {
            mid = (start + end) / 2; // 이분탐색 기준 (짐작하는 b[k] 값)

            if (start == end) {
                return mid;
            }
            
            count = countSmallNum(mid);

            // b 배열에서 현재 mid 이하인 값의 개수가 찾고 있는 k 이상일때
            if (count >= k) {
                end = mid; // 짐작하는 값을 작게
            }
            
            // b 배열에서 현재 mid 이하인 값의 개수가 찾고 있는 k 미만
            else {
                start = mid + 1; // 짐작하는 값을 크게
            }

        }

        return mid;
    }

    // 주어진 mid(limit)을 기준으로
    // 전체 배열에서 그 수까지의 개수
    private static long countSmallNum(long limit) {
        long count = 0;
        long tempLimit = 0;

//        for (int i = 1; i <= n; i++) {
//            tempLimit = Math.min(n * i, limit);
//            count += tempLimit / i;
//        }

        for (int i = 1; i <= n; i++) {
            count += Math.min(limit / i, n);
        }

        return count;
    }
}

 

---

문제를 풀고 난 후

 

이분탐색에서 lower bound, upper bound 와 같은 키워드가 있다는 것을 학습했다.

찾고 있는 요소가 중복, 연속적으로 배치 될 경우에 일반적인 이분탐색과 조금은 다르게 반환해야한다고 하던데, 설명이 직관적으로 와닿지 않았다.

예제를 풀어보며 언제 멈춰야할지를 고려했을 때, start와 end가 같을 때 반환하니 정답이 나왔다. 이분탐색은 항상 이렇게 풀었던 것 같아서 좀 더 연습해봐야겠다. 수학적으로 언제 멈춰야할지를 알고 싶은게 목표다. 끝