백준 1300 K번째 수 Js

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

1300번: K번째 수

 

틀린 내 코드

 

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./이분탐색/1300/input.txt";

const [N, K] = fs.readFileSync(filePath).toString().trim().split("\n");

const ary = Array.from({ length: N }, (v, i) => {
  let result = [];
  let n = 1;
  let index = i + 1;

  for (let k = 0; k < N; k++) {
    result.push(n * index);
    n++;
  }

  return result;
});

let sort = [];

for (let i = 0; i < ary.length; i++) {
  for (let j = 0; j < ary.length; j++) {
    sort.push(ary[i][j]);
  }
}

sort.sort((a, b) => a - b);

function binary(ary, target) {
  let start = 0;
  let end = ary.length - 1;
  let answer = 0;

  let mid = Math.floor((start + end) / 2);
  while (ary[mid] !== target && start <= end) {
    if (target >= mid) {
      answer = ary[mid];
      start = mid + 1;
    } else {
      end = mid - 1;
    }

    mid = Math.floor((start + end) / 2);
  }

  return answer;
}

console.log(binary(sort, K)); //6
console.log(sort, ary);
// ansewr 6
// sort [(1, 2, 2, 3, 3, 4, 6, 6, 9)]
// ary [([1, 2, 3], [2, 4, 6], [3, 6, 9])];

// A = [
//   [1, 2, 3],
//   [2, 4, 6],
//   [3, 6, 9],
// ];
// B = [1, 2, 2, 3, 3, 4, 6, 6, 9];

// 메모리초과;

 

로직

 

문제 그대로 배열을 만들어주고 오름차순 정렬을 한 뒤에 K 번째 수를 이분탐색으로 찾았다.

채점결과는 메모리초과인데 최대 입력이 10만인데 10만X10만 배열을 만드는 순간 메모리초과가 된다.

 

그럼 배열을 만들지 않고 풀어야하는 문제인데

어떻게 풀 수 있을까

 

정답코드

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./이분탐색/1300/input.txt";

let input = fs.readFileSync(filePath).toString().trim().split("\n").map(Number);

const [N, k] = input;

let left = 1;
let right = k;
let answer = 0;

function countOrder(mid) {
  let cnt = 0;

  for (let i = 1; i <= N; i++) {
    cnt += Math.min(parseInt(mid / i), N);
  }

  return cnt;
}

while (left <= right) {
  let mid = parseInt((left + right) / 2);
  let count = countOrder(mid);

  if (count >= k) {
    answer = mid;
    right = mid - 1;
  } else {
    left = mid + 1;
  }
}

console.log(answer);

// N = 3 K = 6
// [1, 2, 3, 4, 5, 6]

// [
  1, 2, 2, 3, 3,
  4, 6, 6, 9
] 
// [ [ 1, 2, 3 ], [ 2, 4, 6 ], [ 3, 6, 9 ] ]

// 1 3 6 left, mid, right
// 3 mid
// 1 3 3 3 for i, parseInt, N, count
// 2 1 3 4 for i, parseInt, N, count
// 3 1 3 5 for i, parseInt, N, count
// 5 cnt

// 4 5 6 left, mid, right
// 5 mid
// 1 5 3 3 for i, parseInt, N, count
// 2 2 3 5 for i, parseInt, N, count
// 3 1 3 6 for i, parseInt, N, count
// 6 cnt

// 4 4 4 left, mid, right
// 4 mid
// 1 4 3 3 for i, parseInt, N, count
// 2 2 3 5 for i, parseInt, N, count
// 3 1 3 6 for i, parseInt, N, count
// 6 cnt

// 4 mid === answer

로직설명

• 입력과 배열 주석은 이해를 돕기 위해 작성한것입니다.
• 1, 3,6 left mid, right 부터, k가 6이니까 문제에서 인덱스는 1번이라는 힌트로 1~6까지 숫자가 있는 배열을 만듭니다.
  • 이 정도 배열은 입력이 10만이라도 메모리초과가 되지않습니다.
• 여기서 mid 값은 3인데 mid 라해서 mid 라고 생각하지말고 기준 값이라고 생각을 해서 count 함수 로직으로 보냅니다.
  • count 함수에서는 for문으로 N만큼 도는데 이유는 N*N 의 배열을 만든다고 했기 때문에 가로로 N 만큼 표현한겁니다.
  • For의 인덱스(i) 에서 mid 기준 값 3을 나눈 값은 3보다 작은 값이 몇개냐라는 의미가 됩니다.
  • 예시로 첫번째 지문에 i = 1 나누기 값(작은 값) =  3(mid/i) n = 3 은 미드 3보다 작은 값이 3개라는 건데 이건 N*N 에서 첫번째 배열 N[0] 번째인 [1, 2, 3] 입니다
  • 두번째 i = 2 계산 값 (mid/i) = 1 n = 3 은 [2, 4, 6] 배열에서 3보다 작은 값이 몇개냐 입니다. 1개죠? 카운터에 누산해줍니다. 카운터 = 4
  • 세번째 i =3 계산 값 (mid/i) = 1 n = 3 은 [3, 6, 9] 배열에서 3보다 작은 값은 중복 값이 있을 수 있으니 3도 포함해줍니다 1개입니다. 카운터는 = 5
  •  K가 6 일때 첫번째 카운터 값은 5입니다. 하지만 우리가 찾는것은 k 가 배열의 몇번째 숫자인지 입니다. 다르게 이야기하면 k 보다 작은 값이 몇개가 있냐 => 카운터 값 >= k 가 됩니다.
  • 일단 카운터는 5였고 k 는 6이니까 더 큰 값에 가서 k 를 찾아야합니다. start 또는 left 를 mid +1 로 옮겨줍니다.
  • 이런식으로 추려나가다보면 k 보다 작은 값 = 카운터번째 순번이 추려집니다. 답은 4

 

저는 지문 그대로 배열을 만들고 거기서 몇번째인지 찾으려고 단순하게 생각해서 메모리초과라는 벽을 만나고...

이게 왜 이분탐색이지라는 생각도하면서 ... 여튼간에 어려웠습니다.

 

좀 더 다른시점으로도 바라보고 접근하면서 논리적인 사고를 길러야할 것 같네요..