백준 1300 - K번째 수

YongHyun·2023년 5월 9일

Java 백준 코딩테스트

백준, 프로그래머스 - 코딩테스트

목록 보기

31/43

문제

시간 제한 2초

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력

B[k]를 출력한다.

예제 입력 1

3
7

예제 출력 1

6

문제 풀이

문제 설명은 이해가 되었는데 풀이 과정이 이해하기 힘든 문제였던 것 같다. 특히 이진 탐색으로 접근해야 한다는 생각까지 정말 오랜 시간이 걸렸던 것 같다.

여러 블로그와 책을 통해 그나마 정리한 내용을 작성해보기로 하였다.

우선 예제 입력 1 에 입력된 데이터를 그림으로 표현해보자면

3 X 3 크기의 배열을 일차원 배열에 넣어준 후 오름차순으로 정렬 후 K번째 수를 구하면 되는 문제이다. 하지만 N은 최대 $10^5$ 이며 이는 전체 배열의 크기는 $10^5$ * $10^5$ 으로 최대 $10^{10}$ 이다. 이는 시간복잡도가 $N^2$ 인 알고리즘을 사용할 수 없다는 것을 파악할 수 있다.

그렇다면 어떠한 방식으로 풀어야 하는가? 우선 B[k] 의 의미를 파악해보자

k = 1 -> B[1] = 1
k = 2 -> B[2] = 2
k = 3 -> B[3] = 2
k = 4 -> B[4] = 3
k = 5 -> B[5] = 3
k = 6 -> B[6] = 4
k = 7 -> B[7] = 6
k = 8 -> B[8] = 6
k = 9 -> B[9] = 9

반복되어 있는 식들을 살펴보면 B[K] = x 라는 의미는 x 보다 작거나 같은 원소의 개수가 최소 k 개이다.

그림으로 표현하자면 B[5] = 3 은 3보다 작거나 같은 원소의 개수가 최소 5 개 이다.

그렇다면 현재 찾고자 하는 결과값은 B[K] 를 출력하는 것인데 K는 이미 문제에서 주어진 상태이니깐 임의의 x 값을 이용해서 x 보다 작거나 같은 원소의 개수가 K 값과 일치하는지를 확인하면 된다.

이때 이진탐색을 사용하여서 중앙값보다 작은 수의 개수를 세어보면서 범위를 절반씩 줄여가가며 B[K]를 찾는것이 이 문제의 핵심이라고 할 수 있다.

그러면 예제 입력 1을 이용해서 차근 차근 이진탐색으로 문제를 풀어보겠다.

현재 입력된 N = 3, K = 7 이다. 2차원 배열에서 K 번째 수는 1 ~ K번째 안에 정답이 있다고 할 수 있다. 시작 인덱스를 1, 종료 인덱스를 7로 정하고 중앙값인 (1 + 7) / 2 = 4 를 구한다.
중앙값보다 작거나 같은 수의 개수는 중앙값을 N으로 나눈 값이다. 단, 나눈 값이 N 보다 크면 N으로 정합니다.

1열은 1로 나눠서 4, 4는 3 보다 크기 때문에 3으로 정한다.
2열은 2로 나눠서 2
3열은 3으로 나눠서 1
총 6개가 나온다.

그렇다면 중앙값 4는 6번째 수보다 큰 수가 될 수 없기 때문에 중앙값 4보다 더 큰 범위에 정답이 있다는 것을 알 수 있다.

중앙값 크기보다 작은 수가 K 보다 작으면 시작 인덱스 = 중앙값 + 1
중앙값 크기보다 작은 수가 K 보다 크거나 같으면 종료 인덱스 = 중앙값 - 1, 정답 변수 = 중앙값

마지막 과정에서 시작 인덱스가 종료 인덱스보다 크므로 이진 탐색을 종료하고 정답값을 저장한 6이 바로 우리가 찾고자 하는 값이다.

이를 코드에 적용하면 다음과 같다.

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

public class 백준_K번째수 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        // x 는 1부터 K 사이의 범위를 가진다.
        long start = 1;
        long end = K;

        while(start < end) {

            long mid = (start + end) / 2;   // 중앙값을 구한다.
            long count = 0;

            /*
             중앙값보다 작은 수는 몇 개인지 계산한다.
             중앙값을 i 번 째 행으로 나누면서 누적 합을 구한다.
             */
            for(int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N);
            }

            /*
                중앙값보다 작은 수의 개수가 K 보다 작다면
                - 시작 인덱스 = 중앙 인덱스 + 1
                중앙값보다 작은 수의 개수가 K 보다 크거나 같으면
                - 종료 인덱스 = 중앙 인덱스 - 1
             */
            if(K <= count) {
                end = mid;
            }else {
                start = mid + 1;
            }
        }
        System.out.println(start);

    }
}