[백준] 1300: K번째 수 - JAVA

in Algorithm on 기타

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

풀이

이차원배열의 각 칸에 i X j 의 숫자들이 들어있다.

이들을 일차원배열에 넣어 정렬했을 때 k번째 숫자를 구해야한다.

풀이 방법이 떠오르지 않아 다른 블로그들의 도움을 받았다.

이차원배열의 각 행들이 구구단으로 이루어져 있다.

구구단을 쭉 나열해보면 다음과 같다.

1단: {1, 2, 3, 4, 5, 6, 7, 8, 9}

2단: {2, 4, 6, 8, 10, 12, 14, 16, 18}

.

.

.

8단: {8, 16, 24, 32, 40, 48, 56, 64, 72}

9단: {9, 18, 27, 36, 45, 54, 63, 72, 81}

이 나열된 숫자에서 예를들어 7보다 작거나 같은 숫자가 몇개인지 구하려면

1단에서는 7 / 1 = 7 으로 7개가 되고,

2단에서는 7 / 2 = 3 으로 3개가 된다.

즉, 이차원배열의 각 행들이 구구단이므로 각 행에서 x보다 작거나 같은 숫자의 개수는 x / i가 된다.

다만 각 행의 개수는 N개를 넘지 않으므로 Math.min(x / i, N) 이 각 행에서 k보다 작거나 같은 숫자의 개수이다.

어떤 수보다 작거나 같은 개수가 k개인 수를 이분탐색을 통해 범위를 줄여나가면서 O(logN)의 시간복잡도로 구할 수 있다.

메모리: 14244KB

시간: 168ms

언어: Java 11

코드

import java.io.*;

public class Main {
    static int N, k;
    static long ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());

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

    private static long binarySearch(long left, long right) {
        if (left >= right) {
            return left;
        }

        long mid = (left + right) / 2;

        long cnt = 0;
        for (int i = 1; i <= N; i++) {
            cnt += Math.min(mid / i, N);
        }

        if (cnt >= k) {
            return binarySearch(left, mid);
        } else {
            return binarySearch(mid + 1, right);
        }
    }

}