Q 1300 K번째 수

💡 문제 요약 및 분석

크기가 NxN 인 이차원 배열 A 를 일차원 배열로 늘어뜨리고 오름차순 정렬 했을 때, K번째 수가 무엇인지 구하자.

💡 알고리즘 설계

✅ 핵심 아이디어 : B[k] = x 일 때, k = x보다 작거나 일치하는 수들의 개수를 말한다. 이분 탐색으로 x를 조절하면서 x보다 작거나 일치하는 수들의 개수가 K가 되는 경우를 찾으면 된다.

1. 입력

   • 표준입력으로 int N, int K 저장한다.

2. 연산

   • left = 1, right = K
   • mid = (left + right) / 2;
   • x보다 작거나 일치하는 수들의 개수는 이렇게 판단할 수 있다. 만약 N=3, x=6 이라면, count += 6/1(6개), 6/2(3개), 6/3(2개) 하면 된다. 다만 문제가 제시한 조건은 이차원 배열이기 때문에 행의 최대 길이는 N이므로 이를 넘으면 안 된다. count += Math.min(6/1,N) ... 으로 작성해야 오류가 없다.
   • 이분탐색 조건은 다음과 같다. count >= K : right = mid - 1; result = mid; count < K : left = mid + 1;
   • 일차원 배열 B는 중복된 숫자가 오름차순으로 정렬된 배열이다. N=3 일 때 [1, 2, 2, 3, 3, 4, 6, 6, 9] 그렇기 때문에 x는 적어도 K보다 같거나 커야한다. 만약 그 반대, K보다 작거나 같은 조건으로 정답을 구하게 된다면 K=7 일 때 4가 정답이 되어버릴 수 있기 때문에 주의해야 한다.

3. 출력

   • result 를 출력한다.

💡 코드

import java.util.Arrays;

public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        int K = read();

        int left = 1;
        int right = K;
        int result = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int count = 0;

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

            if (count >= K) {
                right = mid - 1;
                result = mid;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(result);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n * log K)	O(1)

📎 참고자료

백준 1300번 : K번째 수 - JAVA