K번째 수

문제

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

정답

처음에 다음과 같이 풀이하였는데 답을 제출하기 전에도 시간 제한에 걸릴 것을 알고 있었다. 다만 얼마나 큰 차이가 발생하는지 알고 싶어서 performance.now()함수를 통해 N이 10000이고 k는 100일 때의 소요시간을 계산해보았다. 2213.693750023842ms이었다.

let [N, k] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .split("\n");

const startTime = performance.now();

let B = new Array();
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    B.push((i + 1) * (j + 1));
  }
}

const endTime = performance.now();

console.log(endTime - startTime, B.sort((a, b) => a - b)[k]);

하여 이진 탐색으로 풀이를 해보았다.

let [N, k] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .split("\n");

const startTime = performance.now();

let start = 1;
let end = 10 ** 10;
let result = 0;

while (start <= end) {
  let mid = Math.floor((start + end) / 2);
  let total = 0;
  for (let i = 1; i <= N; i++) {
    total += Math.min(Math.floor(mid / i), N);
  }
  if (total >= k) {
    result = mid;
    end = mid - 1;
  } else {
    start = mid + 1;
  }
}
const endTime = performance.now();

console.log(endTime - startTime, result);

다음 결과 수행시간이 28.361958980560303ms으로 약 100배 더 빠른 성능을 확인할 수 있었다. 하여 각각의 코드에서 시간 복잡도를 계산해보기로 했다.

먼저 반복문으로 구현한 코드 같은 경우

1. B 배열 생성 시 o(N^2)의 시간이 소요된다.
2. B.osrt() 시 평균적으로 O(N^2*log(N^2))의 시간이 소요된다. (배열의 길이가 N^2이므로)
3. 배열의 K번째 원소 출력 시 O(1)

따라서 총 시간 복잡도는 가장 높은 시간 복잡도를 지닌 O(N^2*log(N^2))이 된다.

그럼 이진 탐색으로 풀이한 코드 같은 경우에는 얼마나 시간 복잡도가 발생할까?

1. 이분 탐색은 O(log(end-start))의 시간이 소요된다. 따라서 위의 코드에서는 O(log10^10-1)이다.
2. 루프는 N번 돌기 때문에 O(N)의 시간이 소요된다.

따라서 총 시간 복잡도는 이분 탐색이 반복되는 횟수와 그 안에서의 루프를 곱한 값이 되므로 O(N*log(10^10-1))이다. 이때 상수를 무시하면 O(N*log(N))으로 나타낼 수 있다.

결과적으로

두 시간 복잡도를 비교하면 N만큼의 성능 차이가 발생하는 것을 확인할 수 있다.