백준 11653번

백준 11653번을 풀어보았다.

 

첫번째 풀이는 시간초과가 발생하였다.

let N = Number(require('fs').readFileSync('/dev/stdin').toString())

let primeFactor = 2, output = ''

while (true) {
  while (N % primeFactor === 0) {
    N /= primeFactor
    output += `${primeFactor}\n`
  }

  if (N === 1) break

  let isPrimeNumber = false

  while (!isPrimeNumber) {
    primeFactor += 1
    for (let i = 2; i <= Math.sqrt(primeFactor); i++) {
      if (primeFactor % i === 0) {
        isPrimeNumber = false
        break
      }
      isPrimeNumber = true
    }
  }
}

console.log(output.trim())

 

먼저 나머지가 0이 될 때까지 N을 primeFactor로 나누고 (N에서 하나의 소인수 전부 뽑아내기)

 

이후 primeFactor가 소수가 될 때까지 1 증가 후 2부터 primeFactor의 제곱근까지로 나눠본다. (다음 소인수 찾기)

 

이렇게 그 다음 소수 primeFactor를 발견하면 다시 나머지가 0이 될 때까지 N을 primeFactor로 나눈다.

 

효율성은 고려하지 않고 머릿속에 바로 떠오른 로직을 구현한 것으로,

 

primeFactor의 소수 여부를 판단하는 while (!isPrimeNumber) {} 부분에서 상당한 비효율이 발생한다.

 

이전에 발견한 소수를 활용하지 않고 매번 새롭게 소수를 판별하기 때문인데,

 

예를 들어 primeFactor = 2이고 while (N % primeFactor === 0) {} 과정을 거쳤다면

 

짝수 인수는 더 이상 고려할 필요가 없고 그러므로 짝수 인수의 소수 여부를 판단할 필요도 없다.

 

그러나 위 코드에서는 primeFactor를 1씩 증가시키며 이런 경우에 대해서까지 중복적으로 소수 여부를 판단하고 있다.

 

아래 코드는 이러한 중복을 해결해준다.

let N = Number(require('fs').readFileSync('/dev/stdin').toString())

if (N === 1) return

let output = ''

for (let i = 2; i <= Math.sqrt(N); i++) {
  while (N % i === 0) {
    output += `${i}\n`
    N /= i
  }
}

if (N > 1) {
  output += `${N}\n`
}

console.log(output.trim())

 

while (N % i === 0) 만으로 인수 여부 확인은 물론 소수 여부 확인, 즉 while (!isPrimeNumber) {} 의 역할까지 수행할 수 있다.

 

N이 합성수일 경우 이미 앞서 소인수들에서 처리되었을 것이므로 while (N % i === 0) 이 참이 되도록 하는 i는 무조건 소인수이다.