[백준/nodeJS] 1016. 제곱 ㄴㄴ 수

안녕하세요. 박기린입니다.

백준 1016번 제곱ㄴㄴ수 문제 풀어보겠습니다.

 

 

---

문제 링크

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

 

 

 

 

---

문제 해석

'제곱ㄴㄴ수'가 무엇일까요?

 

 

 

위 메모처럼, n의 제곱으로 나눴을 때 나머지가 없는 수를 제곱ㅇㅇ수라고 표현하고,

그 반대를 제곱ㄴㄴ수라고 문제에서 표현합니다.

 

 

 

 

 

---

정답 코드

const fs = require("fs");
const [min, max] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const isDivided = Array(1000001).fill(false); // max와 min 사이에 들어가는 최대 수, ㄴㄴ제곱이 아닌 수가 true.
let count = 0;

// 에라토스테네스 체를 이용한 제곱 ㄴㄴ 체 만들기
for (let i = 2; i ** 2 <= max; i++) {
  let n = Math.ceil(min / i ** 2); // 걸러내기의 시작지점을 찾는 과정
  // 만약 제곱수에 의해 나눠진다면, 이후 아래의 코드에서 해당 숫자도 true로 지정된다.
  // 만약 안 나눠진다면, 반올림에 의해, 제곱수가되는 그 다음 숫자부터 시작해서 true로 걸러지게 한다.

  while (n * i ** 2 <= max) {
    isDivided[n * i ** 2 - min] = true; // 저장공간 최적화를 위해 -min
    n++;
  }
}

for (let i = 0; i <= max - min; i++) {
  if (!isDivided[i]) count++;
}

console.log(count);

 

 

 

 

 

---

정답 코드 풀이

const fs = require("fs");
const [min, max] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);

min과 max 값을 fs 모듈을 이용해서 입력받는 코드입니다.

 

 

 

const isDivided = Array(1000001).fill(false);
let count = 0;

isDivided는 제곱ㄴㄴ수의 여부를 저장하는 배열입니다.

Max - Min의 최대값이 1000000이기 때문에, 1000001개의 false 값을 담아줍니다.

false이면 제곱ㄴㄴ수, true이면 제곱ㅇㅇ수를 나타냅니다.

 

count는 추후 제곱ㄴㄴ수의 개수를 세는데 이용될 변수입니다.

 

 

 

 

for (let i = 2; i ** 2 <= max; i++) {
  let n = Math.ceil(min / i ** 2);

  while (n * i ** 2 <= max) {
    isDivided[n * i ** 2 - min] = true;
    n++;
  }
}

'에라토스테네스의 체' 비슷하게 '제곱ㄴㄴ수 체'를 만드는 코드입니다.

 

 

  let n = Math.ceil(min / i ** 2);

체의 시작지점 n을 찾는 식입니다.

최소값 min에 i 제곱을 나눈 후, 반올림을 해줍니다. 만약 min이 제곱ㅇㅇ수라면 반올림이 일어나지 않을 것이고, 제곱ㄴㄴ수라면 반올림이 일어날 것입니다.

 

 

 

  while (n * i ** 2 <= max) {
    isDivided[n * i ** 2 - min] = true; // 저장공간 최적화를 위해 -min
    n++;
  }

시작지점 n에 다시 i 제곱을 곱하면, 정수인 제곱ㅇㅇ수를 찾을 수 있습니다.

이후 시작지점 n에 1씩 더해가면서, 제곱ㅇㅇ수의 배수를 찾은 후, isDivded 배열에 true를 넣어줍니다.

 

* 아까 isDivded의 크기를 Max - min의 최대값인 1000000으로 지정했었습니다. 저장공간 최적화를 위해 min 만큼의 크기를 줄였기 때문에, isDivded에 true값을 저장할 때 '-min'을 넣어서 계산해줍니다.

 

 

 

 

for (let i = 0; i <= max - min; i++) {
  if (!isDivided[i]) count++;
}

console.log(count);

마지막으로, isDivided를 탐색하면서 제곱 ㄴㄴ수의 개수를 찾습니다.

1000000개 전부를 탐색할 필요는 없고, max - min 크기만큼만 탐색하면 됩니다.