[백준] 4948 - 베르트랑 공준 (node.js)

pds·2022년 11월 23일

JavaScript algorithm 백준

알고리즘

목록 보기

2/8

처음으로 node.js로 풀게 된 문제라 기념으로 풀이과정을 남겨보았다!

문제링크

문제 요약

입력 숫자 여러개가 주어짐 (1 <= n <= 123456)
n ~ n*2 사이의 소수 개수를 구해라

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19)
또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17, 19, 23)

해결과정

(1) 입력받은 숫자들 중 가장 큰 값을 찾아 그만큼의 소수 여부 배열을 만든다

사실 최대 입력치*2 인 246912 길이만큼 다 만들어도 무방할 것 같다.
에라토스테네스의 체 를 이용해 1부터 최대값 까지의 소수여부 배열을 만든다.

function getPrimes(maxNum) {
  const primes = Array(maxNum).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i < Math.sqrt(maxNum); i++) {
    for (let j = i * i; j <= maxNum; j += i) {
      primes[j] = false;
    }
  }
  return primes;
}

test("getPrimeArray function should return primeArray", () => {
  const expectedPrimes = [false, false, true, true, false, true, false];
  boj.getPrimes(6).forEach((v, i) => {
    expect(v).toEqual(expectedPrimes[i]);
  });
});

(2) 구한 소수 여부 배열을 누적합 배열로 변경해준다

예
input: [false, false, true, false, true, false, true]
output: [false, 0, 1, 1, 2, 2, 3];

어차피 일정 구간 사이에 소수가 몇 개 있나 확인해야하는데

그때그때마다 반복문으로 순회해서 찾지 않고 미리 전부 누적합을 O(n)으로 구해버리고

나중에 두 범위에 대한 인덱스만 찾아서 차를 이용해 개수를 구하려는 속셈이다.

input 숫자가 하나라면 이 방법이 손해이지만 두 개 이상이기 때문에

최악의 경우에는 반드시 효율성이 높아지는 방법이다.

예를 들어 위의 output 배열에서 6과 3 사이의 소수 개수를 구하라 라고 한다면

output[6] - output[3]

이 정답이 되는 것이다.

function getCumulativeSumOfArray(array) {
  const cumulatedArray = array;
  for (let i = 1; i < array.length; i++) {
    cumulatedArray[i] += cumulatedArray[i - 1];
  }
  return cumulatedArray;
}

test("getCumulativeArray function should return cumulativeArray", () => {
  const givenArray = [false, false, true, true, false, true, false];
  const expectedArray = [false, 0, 1, 2, 2, 3, 3];
  expect(boj.getCumulativeSumOfArray(givenArray)).toEqual(expectedArray);
});

(3) 입력받은 숫자 값들을 순회하며 누적합 배열에서 소수 개수를 찾아준다.

아래의 함수를 입력받은 숫자 배열을 map으로 돌아 적용시켜 값을 바꾼 배열로 복사한다던지

바로 forEach 로 콘솔찍어서 정답을 도출한다던지 하면 될 것 같다.

시간이 널널한 문제라 원활한 테스트를 위해 solution 함수에서 map을 썼다.

function getCountOfArrayByRange(start, array) {
  return array[start * 2] - array[start];
}

test("getCountArray function should return count value", () => {
  const givenArray = [false, 0, 1, 2, 2, 3, 3];
  const expectedValue = 1;
  expect(boj.getCountOfArrayByRange(2, givenArray)).toEqual(expectedValue);
});

풀이코드

const INPUT = require("fs").readFileSync("/dev/stdin").toString().split("\n");

function inputToNumArray() {
  const array = [];
  for (let i = 0; i < INPUT.length; i++) {
    if (INPUT[i] === "0") {
      return array;
    }
    array.push(INPUT[i]);
  }
  return array;
}

function solution(nums) {
  const maxValue = Math.max(...nums) * 2;
  const primes = getPrimes(maxValue);
  const cumulatedPrimes = getCumulativeSumOfArray(primes);

  return nums.map((value) => getCountOfArrayByRange(value, cumulatedPrimes));
}

function getPrimes(maxNum) {
  const primes = Array(maxNum).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i < Math.sqrt(maxNum); i++) {
    for (let j = i * i; j <= maxNum; j += i) {
      primes[j] = false;
    }
  }
  return primes;
}

function getCumulativeSumOfArray(array) {
  const cumulatedArray = array;
  for (let i = 1; i < array.length; i++) {
    cumulatedArray[i] += cumulatedArray[i - 1];
  }
  return cumulatedArray;
}

function getCountOfArrayByRange(start, array) {
  return array[start * 2] - array[start];
}

solution(inputToNumArray()).forEach((v) => console.log(v));

exports.solution = solution;
exports.getPrimes = getPrimes;
exports.getCumulativeSumOfArray = getCumulativeSumOfArray;
exports.getCountOfArrayByRange = getCountOfArrayByRange;

테스트코드

const boj = require("./boj4948");

test("getPrimeArray function should return primeArray", () => {
  const expectedPrimes = [false, false, true, true, false, true, false];
  boj.getPrimes(6).forEach((v, i) => {
    expect(v).toEqual(expectedPrimes[i]);
  });
});

test("getCumulativeArray function should return cumulativeArray", () => {
  const givenArray = [false, false, true, true, false, true, false];
  const expectedArray = [false, 0, 1, 2, 2, 3, 3];
  expect(boj.getCumulativeSumOfArray(givenArray)).toEqual(expectedArray);
});

test("getCountArray function should return count value", () => {
  const givenArray = [false, 0, 1, 2, 2, 3, 3];
  const expectedValue = 1;
  expect(boj.getCountOfArrayByRange(2, givenArray)).toEqual(expectedValue);
});

test("solution function should return expected value", () => {
  const inputs = [1, 10, 13, 100, 1000, 10000, 100000];
  expect(boj.solution(inputs)).toEqual([1, 4, 3, 21, 135, 1033, 8392]);
});