백준 19637 node.js

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

실버3 이라고 너무 쉽게 생각한 것 같다.. ㅠ

가장 처음 시간복잡도를 전혀 생각하지 않고 푼 코드.
N,M < 10,000 이므로 O(N*M) 인 코드가 통과 될 리 없었다.. ㅠ

const fs = require('fs');
const file = process.platform === 'linux' ? 'dev/stdin' : '../stdin.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const titleList = [];
for (let i = 0; i < N; i++) {
  const [keyword, value] = input[i + 1].split(' ');
  titleList.push([Number(value), keyword]);
}
titleList.sort((a, b) => a[0] - b[0]);

for (let i = 0; i < M; i++) {
  const value = Number(input[i + N + 1]);
  for (let j = 0; j < titleList.length; j++) {
    if (titleList[j][0] >= value) {
      console.log(titleList[j][1]);
      break;
    }
  }
}

수정한 코드

두가지 포인트

1. titleIndex 를 하나씩 증가시키며 최대 M번만 반복하도록 하였음.
   결과적으로 O(N*M) 에서 O(N)번으로 변경됨.
   이진탐색으로 많이 푸는 것 같은데, 이진탐색은 O(Nlog(M)) 이 되므로 이 방법이 시간복잡도가 더 낮습니다.

2. console.log 를 M번 수행하는 것이 아닌, 한번에 수행하도록 변경
   (이론적으로 시간 복잡도 상에서는 큰 차이는 없지만 이렇게 안하면 시간초과가 된다)

const fs = require('fs');
const file = process.platform === 'linux' ? 'dev/stdin' : '../stdin.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const titleList = [];
for (let i = 0; i < N; i++) {
  const [keyword, value] = input[i + 1].split(' ');
  titleList.push([Number(value), keyword]);
}

const valueList = input.slice(N + 1).map((el, i) => [Number(el), i]);
valueList.sort((a, b) => a[0] - b[0]);
let titleIndex = 0;
const results = [];
for (let i = 0; i < M; i++) {
  const currentValue = valueList[i][0];
  while (true) {
    const [titleValue] = titleList[titleIndex];
    if (currentValue > titleValue) titleIndex += 1;
    else break;
  }
  results.push([valueList[i][1], titleList[titleIndex][1]]);
}
console.log(
  results
    .sort((a, b) => a[0] - b[0])
    .map((el) => el[1])
    .join('\n')
);

이진탐색

const fs = require('fs');
const file = process.platform === 'linux' ? '/dev/stdin' : '../stdin.txt';
const input = fs.readFileSync(file).toString().trim().split('\n');

const [N, M] = input[0].split(' ').map(Number);
const titleList = [];
for (let i = 0; i < N; i++) {
  const [keyword, value] = input[i + 1].split(' ');
  titleList.push([Number(value), keyword]);
}

function binarySearch(value) {
  let left = 0;
  let right = titleList.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (value <= titleList[mid][0]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return titleList[left][1];
}

const results = [];
for (let i = 0; i < M; i++) {
  const value = Number(input[i + N + 1]);
  results.push(binarySearch(value));
}

console.log(results.join('\n'));

아... 이론적으론 위에가 더 빠를걸요..?