[백준] 1300 K번째 수 java 이해하기 쉬운 풀이^^ 🌟

1. 문제 설명

문제 링크

2. 접근 방식

KEY WORD: BINARY_SEARCH

이번 문제의 주어진 배열의 크기는 10^5이다. 주어진 시간 제한이 2초이므로, 2억 번의 연산 횟수 내에 문제를 풀어야 한다. 만약 해당 문제를 브루트 포스로 접근해, 모든 2차원 배열을 돌겠다고 생각하면, 연산 횟수가 10^5의 제곱인 10 억번이 되어 문제를 풀지 못한다.

해당 문제는 이분 탐색(binary_search)을 이용해 풀 수 있다. 고난도 이분 탐색 문제가 늘 그렇듯, 도대체 뭐에 대해서 이분 탐색을 해야하는지 감 잡기가 힘들다. 그래서 거기서 부터 시작 하겠다.

(1) 무엇에 대해서 이분 탐색을 해야 하는가?

먼저 문제에서 주어진 B[]이란 배열에 대해서 알아볼 필요가 있겠다. B[k] = x 이것이 무엇을 뜻하는가?
해당 표현의 뜻은 x란 수보다 작거나 같은 수가 최소 k개 있다는 뜻이다. 이번 문제는 관점의 전환이 필요한데, k 번째 수를 찾겠다는 생각을 하지 말고, x를 하나 택해서 해당 수가 몇 번째 수인지 구해서 k까지 나아간다.라고 생각을 해야한다.
'어? x가 k보다 후순위네? x를 줄여야지.', '어? x가 k보다 앞에 있네 그럼 x를 높여야지' 와 같이 up & down을 해나가는 것이 좋다.

(2) 그럼 x가 몇 번째 수인건 어떻게 알아요?

생각해보니 그렇다. x가 몇 번째 수인지 구할려면 1부터 또 다 세어야 하는 것 아닌가? 하지만 해당 문제의 1차원 배열이 사실 A[i] [j] = i*j 를 만족하는 2차원 배열의 값들을 오름 차순 정렬한 것이면 알면, 규칙성을 이용하여, 브루트 포스를 하지 않고도 몇 번째 수인지 확인할 수 있다. 일단 2차원 배열일 때의 모습을 보자.

A[] []	1	2	3	4
1	1	2	3	4
2	2	4	6	8
3	3	6	9	12
4	4	8	12	16

규칙성이 보이는가?
행 별로 잘라서 보기 바란다. 그러면 해당 2차원 배열이 구구단의 형태를 하고 있음을 알 수 있다.
2차원 배열에서 x가 몇 번째 수인지 구하려면, 각 행을 담당하는 n으로 x를 나눴을 때 나오는 몫들의 다 더하면 된다.
(x/n의 몫의 총합)

예를 들어 x=4라고 해보자. 4가 해당 4*4 배열에서 몇 번째 수일까?

A[] []	1	2	3	4	x = 4 일때 x/n의 몫
1	1	2	3	4	4
2	2	4	6	8	2
3	3	6	9	12	1
4	4	8	12	16	1

총합은 8이다. 일일히 세어보면, 4보다 작거나 같은 수가 총 8개 존재한다는 것을 알 수 있다.
그러면 x = 12면은 몇 번째 수일까?

A[] []	1	2	3	4	x = 12 일때 x/n의 몫
1	1	2	3	4	12 => 4
2	2	4	6	8	6 => 4
3	3	6	9	12	4
4	4	8	12	16	3

보다시피 1과 2의 경우 각각 몫이 12와 6이 나왔지만 4까지로 잘랐다. 이유는 각 행 별로 배수의 최대 갯수가 N개이기 때문이다. 여기서 알 수 있는 것은 x가 몇 번째 수인지 구할 때, Math.min(N, x/n)이라는 것을 알 수 있다.
x = 12일 때, x보다 작거나 같은 수는 총 15개이다.

왜 몫의 총합이 곧 그 수의 위치를 말해줄까?

각 구구단의 배수가 되는 수를 n이라 할 때, x/n의 몫은 해당 구구단에서 몇 번째 수까지 x의 이하 값인지 알려주기 때문이다. n = 2, x = 12일 때, 2의 1배수, 2의 2배수, 2의 3배수, 2의 4배수, 2의 5배수 2의 6배수는 x보다 작거나 같다.

(3) UpperBound, LowerBound 뭐 써야 해요?

해당 문제는 Lower Bound를 써야 한다.
Lower Bound란, 이분탐색으로 target 값의 시작 위치를 찾는 것이다. 막 특별한 것은 아니고, 중간값 < 타겟 일 때는 left = mid+1 로 올라가고, 중간값 => 타겟이면 right = mid-1 로 내려간다.
자세한 설명은 다음 블로그에 자세히 적혀 있다. 블로그: Lower Bound & Upper Bound 개념 및 구현

달라진 점은 중간값 == 타겟이어도 내려간다는 것이다! 이렇게 하면 찾고자 하는 target 값의 첫 시작 위치를 알 수 있게 된다. 다음 예시에서는 target = 3이라고 해보자. 그러면 다음과 같이 된다.

index	0	1	2	3	4	5	6	7	8	9
value	1	2	2	3	3	3	5	6	8	0
	left			lower bound(3)	mid					right

(arr[mid] = 3 으로 이미 결과는 찾았지만, right는 index 3까지 내려오게 된다. 이후 left와 right는 3에서 만나게 되고, 이때 mid 값은 (3+3) /2 로 또 3이 되므로 결국 right는 index:2 까지 내려온다. 이때 start 값이 바로 lower bound가 바라는 target의 시작 위치가 되는 것이다.)

왜 Lower Bound를 써야해? 그냥 x가 k번째 수가 되었을 때 바로 탈출하면 안돼?

라는 의문이 들 수 있다. 결론은 x가 k번째 수일 때 바로 탈출하면, 해당 x가 2차원 배열에서 존재하지 않았던 수일 수 있다는 것이다.

x를 산정해서, 그 x가 몇 번째 값인지로 up or down을 결정하므로 해당 이분 탐색에서는 x=index k=value이다. N=5인 경우를 1차원 배열로 나타내보겠다.

x	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
k	1	2	5	8	10	12	12	14	15	17	17	19	19	19	21	22	22	22	22	24	24	24	24	24	25

여기서 구해야 하는 K = 17이라고 해보자.
Loop1: start=1, end=17, mid=9
Loop2: start=10, end=17, mid=13
Loop3: start=10, end=12, mid=11
=> x=11일 때, 이미 17번째 수이다. 하지만, 11은 NN 배열에 존재하는 수가 아니다! (Lower Bound 지속)
Loop4: start=10, end=10, mid=10
=> 이 다음에는 Lower Bound에 따라 end가 9로 줄어들면서 start<=end가 어긋나서 이분탐색이 종료된다.
이때 start가 가리키는 10이 k=17의 시작점임을 알 수 있다. k가 바뀌는 시작점에 있는 값은 무조건 존재한다.
왜냐하면 x가 K번째 수라는 의미는 x보다 작거나 같은 값이 K개 있다는 소리인데, 그것의 최소 기준을 맞추려면, 배열 내에 있는 어느 원소여야 딱 맞아 떨어지기 때문이다. 따라서 LowerBound를 통해 우리가 찾는 target 값의 시작 위치를 선점해야 한다.

3. 코드 분석

import java.io.*;
import java.util.*;

public class Main {
    static int N,M;
    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());

        // S와 E는 B[] 배열의 값이다. 예를 들어 B[i] = 2 라면 오름차순에서 i번째 수는 2라는 소리이다.
        long S = 1;
        long E = K;

        while(S<=E){
            long x = (S+E)/2;
            long loc = 0;
            for (int i = 1; i <= N; i++) {
                long now = Math.min(x/i, N);
                if(now != 0) loc += now;

                else break;
            }
            if(loc >= K) E = x-1;
            else {
                S = x+1;
            }
        }
        System.out.println(S);
    }
}