[바미] K번째 수

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0]);
const k = parseInt(input[1]);

function countLessOrEqual(x) {
    let count = 0;
    for (let i = 1; i <= N; i++) {
        count += Math.min(Math.floor(x / i), N);
    }
    return count;
}

function findKthNumber(N, k) {
    let low = 1;
    let high = N * N;
    let result = 0;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (countLessOrEqual(mid) >= k) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return result;
}

const kthNumber = findKthNumber(N, k);
console.log(kthNumber);

문제 해설

이 문제는 𝑁 * 𝑁배열의 특정한 위치의 값을 찾는 문제로, 완전한 배열을 생성하지 않고도 이 값을 효율적으로 찾아내야 합니다.

마찬가지로 이 문제 또한 이진 탐색을 사용하여 풀면 좋은 문제입니다.

 

𝑁 * 𝑁배열의 값을 직접 생성하는 대신 𝑖 * 𝑗형태로 값을 구할 수 있다는 것을 이용해야 합니다.

먼저, k번째 작은 값을 찾기 위해 이진 탐색을 사용합니다.

그 후 각 중간 값에 대해 그 값보다 작거나 같은 값의 개수를 세어 k번째 값이 무엇인지 찾아내면 되죠.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

이진 탐색의 시간 복잡도는 𝑂(log ⁡𝐻)이며, 각 단계에서 모든 나무 높이를 합산하는 데 𝑂(𝑁)가 소요됩니다.

따라서 전체 시간 복잡도는 𝑂(𝑁 log ⁡𝐻)입니다. 

여기서 𝐻는 가장 높은 나무의 높이를 의미합니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

공간 복잡도는 입력 데이터와 해시셋을 저장하는 데 필요한 𝑂(𝑁)이 됩니다.

이진 탐색 과정에서 추가적인 메모리가 거의 필요하지 않기 때문에 전체 공간 복잡도는 𝑂(𝑁)이 됩니다.