[백준 1300 파이썬, node.js] K번째 수 (골드2, 이분 탐색)

배코딩·2022년 1월 5일

JavaScript node.js ps 백준 알고리즘 이분 탐색 코딩테스트 파이썬

PS(백준)

목록 보기

35/118

알고리즘 유형 : 이분 탐색
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

N, K = int(input()), int(input())
start, end = 1, K

def findOrder(n):
    count = 0
    for i in range(1, N+1):
        count += min(n // i, N)
        
    return count

while start <= end:
    mid = (start + end) // 2
    order = findOrder(mid)
    
    if order >= K:
        end = mid - 1
    else:
        start = mid + 1
        

print(start)

소스 코드(node.js)

'use strict'
const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split("\n");
const [N, K] = input.map(Number);

function findOrder(n){
    let count = 0;
    for (let i=1; i<N+1; i++){
        count += Math.min(parseInt(n/i), N);
    }
    return count;
}

function findNum(){
    let start = 1;
    let end = K;
    
    while (start <= end){
        let mid = parseInt((start + end) / 2);
        let order = findOrder(mid);
        
        if (order >= K){
            end = mid - 1;
        } else{
            start = mid + 1;
        }
    }
    
    return start;
}

console.log(findNum());

풀이 요약

구현은 정말 간단한데, 이분탐색을 적용하는게 상당히 어려운 문제였다.

왜 이분 탐색을 써야하는가, 쓴다면 탐색 범위를 무엇으로 잡아야하는가, 분할은 무엇을 기준으로 분할할 것인가. 이 3가지가 핵심이라고 생각한다.

단순히 A에 해당하는 모든 수를 arr에 구하고, arr를 정렬한 뒤 arr[k]를 인덱싱한다고 치면, A를 구하는 것만 최대 $10^{10}$ 이다. 당연히 TLE이다.

그럼 이제 이분 탐색으로 어떻게 풀지 생각해보자.

탐색 범위는 1부터 K까지의 수, 그리고 여기에는 B[K]가 포함되어 있다.

분할 기준은 탐색 수 n의 서수, 즉 탐색 중인 수 n이 수열 B에서 몇 번째 수인지를 나타내는 값 order가 분할 기준이다.

요약하면, 1부터 K까지 수를 이분 탐색으로 돌면서, 탐색 중인 수가 몇 번째 수인지에 따라 탐색 범위를 수정한다.

왜 범위가 A에서 가장 큰 수인 (NxN)가 아니라 K까지일까?

이 것은 직관적으로, NxN에 대해 B를 구해놓고 나열해보면 알 수 있다.

테스트케이스의 경우에, B를 나열하면 [1, 2, 2, 3, 3, 4, 6, 6, 9] 이다.

B[i]는 i보다 항상 작거나 같다는 것을 알 수 있다. 그래서 B[k]를 찾으므로 탐색 범위를 k까지만으로 둔 것이다. 사실 그냥 (NxN)까지로 둬도 문제는 통과한다.

분할 기준을 알아보기에 앞서, 탐색 중인 수 n에 대해, n이 B에서 몇 번째 수인지를 알아보는 방법을 설명하겠다.

n이 B에서 몇 번째 수인지를 알기 위해선, n보다 작거나 같은 수 중에서 두 자연수의 곱으로 나타내어지는 수가 A에서 몇 개 있는지 알면, 그게 곧 B에서의 서수이다.

테스트케이스를 예시로 살펴보자.

$\begin{pmatrix}1&2&3\\2&4&6\\3&6&9\\\end{pmatrix}$

여기서 6은 B에서 몇 번째 수일까?

A에서, 각 행의 수들은, 행 row의 배수들이다. 예를 들어, 2행의 2, 4, 6은 2의 배수들이다.

이로부터, 모든 행에 대해, 각 행 row에 대해 row의 배수들 중 6까지의(6 포함) 배수들만 카운팅해준 것들을 모두 합하면, 그 것이 6의 B에서의 서수라는 것을 알 수 있다.

그리고 각 행 row에서, min(6//row, N)이 행 row에서의 6보다 작거나 같은 자연수 곱 수의 개수이다. 식이 저런 이유는, 만약 8의 경우에, 2행에서 최대 카운팅 수는 열의 개수인 N이어야 하는데 8//2 = 4가 되버리기 때문이다.

6의 경우 min(6//1, 3) + min(6//2, 3) + min(6//3, 3) = 8이다.

분할 기준에 따라 어떻게 분할하며, 그렇게 나누는 이유를 알아보자.

분할 기준은 탐색 중인 수 mid에 대해, mid가 B에서 order번째 수일 때, order가 기준이다. 이 order는 6번에서 설명한 방법을 함수로 구현해서 구해주면 된다.

그리고, 분할은 order가 K보다 크거나 같을 때 end = mid - 1로 탐색 범위를 좁히고, order가 K보다 작을 때는 start = mid + 1로 둔다.

왜 이렇게 나눌까?

우선 order < K인 경우를 생각해보자. 내가 3를 탐색 중이고 order가 5가 나온 상황을 생각해보자.

이 경우엔 3은 구하는 정답 n의 서수인 7보다 낮은 5번 째이므로, 당연히 n은 3보다 큰 수이다. 그러므로, 탐색 범위를 start = mid + 1로, 오른쪽 방향으로 좁혀준 것이다.

반대로 order > K인 경우를 생각해보자. 내가 8를 탐색 중이고 order가 9가 나온 상황을 생각해보자.

이 경우엔 8(9번째임)은 구하는 수 n(7번째임)보다 뒤에 있으므로, 탐색 범위를 8보다 작게 설정해주어야 한다. (end = mid + 1)

이제 order == K인 경우만 남았다. 이 때는 어떻게 해야할까.

order가 K, 즉 7과 같을 수 있는 경우는, 실제 7번째 수인 6보다 같거나 크고, B에서 6 다음으로 큰 수인 9보다 작은 수들이다.

B에서 6, 7, 8은 A에서, 자기 자신보다 작거나 같은 두 자연수의 곱의 개수가 6의 경우에서와 똑같다. 그런데 B에서 6 다음으로 큰 수인 9부터는, A에서, 자기 자신보다 작거나 같은 두 자연수의 곱의 개수를 셀 때 자신인 9도 들어가므로, order가 8이 되버리기 때문이다.

그래서 이 경우에는 마찬가지로 end = mid - 1로 설정해주면 된다. 한 편, B에 6이 두개 들어있는데, 이 경우에도 6을 탐색 중일 때, A에서, 자기 자신보다 작거나 같은 두 자연수의 곱의 개수를 카운팅할 때 6이 두 번 카운팅되므로, 내가 8번째 6를 골랐더라도 end = mid - 1로 두어 7번째 6으로 이동할 수 있게 되니 이 케이스도 걱정없다.

이런 식으로 끝까지 가면, end는 order == K인 경우 중 가장 작을 때 마지막으로 한번 더 end = mid - 1를 하고 그 순간에 order가 K보다 작아졌으므로 더 이상 end를 갱신하지 않기에, end는 목표로 하는 값 바로 직전의 순서에 있는 값이 되게 된다.

start는 order < K인 동안 계속 mid + 1로 갱신하다가, order < K인 수들 중 마지막 제일 큰 수에서 mid + 1를 수행하고, 그 순간 order >= K가 되버리므로 start 갱신은 거기서 끝이 난다. 이 때의 start는 order == K인 수 중 가장 작은 수에서 멈추게 된다. order < K인 경우를 벗어나자마자 당장 갱신이 멈추기 때문이다. 예를 들어 4, 5는 order가 6인데, 실제 A에서 order 6인 수는 4이다. 즉, order 6인 수 중 가장 작은 수이다.

그러면 while 조건을 위배하여 벗어나게 되고, 그 때의 start가 바로 구하는 수 B[K]이다.