백준 1300번 K번째 수 JavaScript 풀이 [이진 탐색]

백준 1300번 K번째 수 문제를 자바스크립트로 이진 탐색 알고리즘을 이용해서 풀어보았다. 

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

 

어려웠다 ㅠㅠㅠ

만약 B 배열이 [1, 2, 2, 3, 3, 4, 6, 6, 9] 이렇게고, k=7이면 답은 6이다.

→ mid = 5로 시작해서, 5(mid)보다 작거나 같은 데이터의 수가 7(k)개 이상이 될 때, 이 mid를 출력하면 답이다.

-> mid = 5일 때는, 5보다 작거나 같은 데이터의 수가 6개이고, 이 개수가 k=7보다 작으므로 mid값을 증가시키기 위해 start = mid + 1 해줘야 함

반대로, 개수가 k보다 크면 mid 값을 감소시켜줘야 하므로 end = mid 해줘야 함

 

1) 실패 ->  mid보다 작거나 같은 데이터의 수를 구할 때 이중 for문 사용해서 시간 초과

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

// n x n 배열 A, A[i][j] = i * j, B[k] 구하기
let [n, k] = input.map(Number);
let start = 1;
let end = n * n;
let result = 0;

// 이분 탐색 
while (start < end) {
  let mid = parseInt((start + end) / 2);
  let count = 0;
  for (let i=1; i<=n; i++) {
    for (let j=1; j<=n; j++) {
      if (mid >= i * j) count++;
    }
  }

  if (count == k) {
    result = mid;
    break;
  }
  else if (count > k) end = mid;
  else start = mid + 1;
}
console.log(result)

 

2) 성공

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

// n x n 배열 A, A[i][j] = i * j, B[k] 구하기
let [n, k] = input.map(Number);
let start = 1;
let end = n * n;
let result = 0;

// 이분 탐색 
while (start <= end) {
  let mid = parseInt((start + end) / 2);

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

  // mid보다 작거나 같은 원소의 개수가 k보다 작으면 mid를 높여서 개수를 늘리기 위해 start를 높임
  if (count >= k) {
    result = mid;
    end = mid - 1;
  }
  else start = mid + 1;
}
console.log(result)

 

개수 구할때는 행을 순회하면서, 각 행마다 n개씩 있으니까, 조건을 만족하는 수가 최소 1개부터 최대 n개까지 나온다.

그래서 Math.min을 사용해서 mid/i와 n 중 최소인 것을 찾은 것이고,

parseInt(mid / i)를 한 이유는 수식으로 설명해보자면 (노션으로 적고 옮겨붙임) 아래와 같다.

단, 아래에서는 mid가 n보다 작거나 같다고 가정한 경우이다.