백준_13909: 창문닫기 (node.js/JavaScript)

➡️ 문제: 창문닫기

 

🍯 제출

let n = require('fs').readFileSync(0).toString().trim();
let count = 0;

for (let i = 1; i * i <= n; i++) {
  count++;
}

console.log(count);

 

⛲️ 과정

 

다음은 처음에 제출하고 메모리 초과된 코드이다 ㅜ.ㅜ

let n = require('fs').readFileSync(0).toString().trim();
let testarr = Array(Number(n) + 1).fill(0);

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n / i; j++) {
    if (testarr[i * j] == 1) {
      testarr[i * j] = 0;
    } else {
      testarr[i * j] = 1;
    }
  }
}

let result = testarr.filter((e) => e == 1).length;
console.log(result);

 

위 코드는 주어진 n값만큼 배열 testarr을 생성하고, 그 배열의 값을 반복적으로 토글하고, 마지막에 1로 설정된 값만 filter해서 남긴 후 그 배열의 length를 찍어준다.

 

뭘 고쳐야할까 생각해보니까 조건에 >>창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.<< 가 있었다

첫번째 시도에서는 n이 큰 경우 testarr 배열이 짱 커지니까 메모리 초과가 발생한 것으로 예상됐다

 

... 

 

 그래서 문제를 다시 분석했다.

주어진 수 n의 약수의 개수만큼 토글이 발생한다. 그런데 이때 약수의 개수가 짝수인지 홀수인지가 중요한데,

0을 기본값으로 두고 토글을 시작한다 가정했을 때

 

짝수 개의 약수를 가진 숫자-> 짝수 번 토글되면 최종적으로 0

홀수 개의 약수를 가진 숫자-> 홀수 번 토글되면 최종적으로 1

 

그럼 우린 약수의 개수가 홀수인 경우를 구하면 되는데, 생각해보면 a*b = n 이 되니까 약수는 a, b로 쌍을 이룬다.

 

이때 n이 36이라고 치면 약수 중 6, 6으로 같은 값을 쌍으로 가지는 경우가 발생하는데, 36의 약수의 갯수는 9개이다. 

이것처럼 같은 값을 쌍으로 약수로 가지는 경우를 찾으면 약수의 갯수가 홀수가 된다!

그래서 최종 제출 코드에 i * i <= n 조건을 만족할 때 count를 ++했다.