[JS] 백준 1300번 K번째 수

---

문제 링크

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

풀이 전략

B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.

코드 

const fs = require("fs");
const [n, k] = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(/\s/)
    .map(Number);

solution(n, k);

function solution(n, k) {
    let lt = 1;
    let rt = n * n; // k의 최대값은 n * n이기 때문에 rt는 n * n

    while (lt <= rt) {
        const mid = Math.floor((lt + rt) / 2);

        if (orderConfirm(mid) >= k) rt = mid - 1; // 순서를 확인하여 k보다 크거나 같다면 rt를 mid보다 작게한
        else lt = mid + 1; // 정답을 도출하기위한 answer변수를 쓰지 않기 위해 if문 안의 두 변수들을 바꾸었다.
    }

    console.log(lt);
}

function orderConfirm(mid) {
    let cnt = 0;

    for (let i = 1; i <= n; i++) {
        cnt += Math.min(n, Math.floor(mid / i)); // n의 인덱스 범위를 넘어가면 n보다 큰 인덱스는 없기 때문에 n으로 변경.
    }

    return cnt;
}

 

회고

이분탐색 알고리즘을 사용해야함을 떠올리기 힘들었다. 직접 배열을 만들어보고 규칙을 파악한 후 그리고 k와 n의 범위가 굉장히 넓다는 것을 알고 난후에야 이분탐색을 알게되었다. 아직 내 것으로 제대로 만들지 못하였다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)