백준 11653번 Node.js 풀이

문제 링크

- 처음 풀이 (시간초과)

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

let N = Number(input);

let answer = "";
let decArr = [];

for (let i = 2; i <= N; i++) {
  let arr = [];

  for (let j = 1; j <= i; j++) {
    if (i % j === 0) {
      arr.push(j);
    }
  }

  if (arr.length === 2) {
    decArr.push(i);
  }
}

for (let k = 0; k < decArr.length; k++) {
  if (N <= 1) {
    break;
  }
  if (N % decArr[k] === 0) {
    answer += decArr[k] + "\n";
    N = N / decArr[k];
    k = -1;
  }
}

console.log(answer.trim());

- 다른 풀이

const input = `9991`;

let N = Number(input);

let i = 2;

let decArr = [];

while (true) {
  if (N % i === 0) {
    decArr.push(i);
    N = N / i;
    i = 2;
  }

  i++;

  if (N <= 1) {
    break;
  }
}

console.log(decArr);

아예 i를 지정해줌으로써 하나씩 값을 비교해보는 방법이다. 이런 경우 시간 복잡도가 최대 O(n)이어서 시간 초과가 발생하지 않는다.