[BaekJoon] 1300 K번째 수 (Java)

1.  문제 링크

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

2.  문제

요약

• 크기가 N x N인 배열 A에 들어있는 수 A[i][j]는 i * j 입니다.
• 이 수를 일차원 배열 B에 넣으면 B의 크기는 N x N이 될 것입니다.
• B를 오름차순 정렬했을 때, B[k]를 구하는 문제입니다.
• A와 B의 인덱스는 1부터 시작합니다.
• 입력: 첫 번째 줄에 100,000보다 작거나 같은 자연수인 배열의 크기 N이 주어지고 두 번째 줄에는 min($10^9, N^2$)보다 작거나 같은 자연수인 k가 주어집니다.
• 출력: 첫 번째 줄에 B[k]를 출력합니다.

3.  소스코드

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

public class Main {
    static int N, k;
    static long answer;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        k = scanner.nextInt();
    }

    static void solution() {
        binarySearch(1, k);
        System.out.println(answer);
    }

    static void binarySearch(int min, int max) {
        int left = min, right = max;
        while(left <= right) {
            int mid = (left + right) / 2;
            long count = 0;

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

            if(count < k) {
                left = mid + 1;
            } else {
                answer = mid;
                right = mid - 1;
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• B의 최대 길이가 $10^5 × 10^5$이므로 오름차순으로 정렬을 한다면 시간 초과가 발생합니다.
• 그렇기 때문에 임의의 수 x보다 작거나 같은 원소의 수가 k개인 x를 찾는 이분탐색 문제로 변경할 수 있습니다.
  • 최소를 1, 최대를 k로 놓고 시작합니다.
  • 중간값을 찾고 해당 값보다 작거나 같은 원소의 개수를 구합니다.
    • 이는 중간값을 1부터 N까지 나누면서 찾을 수 있습니다.
    • 각 행을 보면 1단, 2단, 3단... 이렇게 바라볼 수 있는데 만약 임의의 수 x가 5라면, 1단에서는 5보다 작거나 같은 수의 개수가 1, 2, 3, 4, 5로 5개, 2단에서는 2, 4로 2개, 3단에서는 3으로 1개가 됩니다.
    • 그런데 N이 3이라면, 각 행에서는 3보다 큰 수는 나올 수 없습니다.
    • 그렇기 때문에 1단에서는 1, 2, 3으로 3개, 2단에서는 2로 1개, 3단에서는 3으로 1개가 됩니다.
    • 즉, 임의의 값을 해당 행의 인덱스로 나눈 몫과 N을 비교하여 더 작은 값이 해당 행에서 임의의 수 x보다 작거나 같은 원소의 수가 됩니다.
      • min(x / row, N) (row = 해당 행의 인덱스)
  • 만약 해당 값보다 작거나 같은 원소의 개수가 k보다 작다면 왼쪽 포인터(최소값)를 mid + 1로 변경합니다.
  • 만약 해당 값보다 작거나 같은 원소의 개수가 k보다 크거나 같다면 우선 답을 해당 값으로 갱신하고 오른쪽 포인터(최댓값)를 mid - 1로 변경합니다.
    • 해당 수가 여러 개 존재한다면 실제로 그 수가 k번째에 존재한다고 하더라도 해당 수보다 작거나 같은 수의 개수를 구하면 k보다 크게 나올 것이기 때문에 이렇게 진행합니다.