[백준1644_자바스크립트(javascript)] - 소수의 연속합

🔴 문제

소수의 연속합

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const n = +fs.readFileSync(path).toString().trim();
const memo = Array(n + 1).fill(1);
const primeNumber = [];

// n까지의 모든 소수를 구한다
for (let i = 2; i <= Math.sqrt(n); i++) {
  if (memo[i] === 0) continue;

  for (let j = i + i; j <= n; j += i) {
    memo[j] = 0;
  }
}

for (let i = 2; i <= n; i++) {
  if (memo[i]) primeNumber.push(i);
}

// 투포인터를 사용해 소수의 연속합의 개수를 카운팅한다.
let left = 0;
let right = 0;
let ans = 0;
let sum = primeNumber[right];

while (left <= right && right < primeNumber.length) {
  if (sum < n) {
    right += 1;
    sum += primeNumber[right];
  } //
  else if (sum > n) {
    sum -= primeNumber[left];
    left += 1;
  } //
  else {
    ans += 1;
    sum -= primeNumber[left];
    left += 1;
    right += 1;
    sum += primeNumber[right];
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

투포인터 유형 문제
n까지의 소수 구하기 -> 소수의 연속합 개수 구하기 두 단계로 문제를 풀이해주면 된다.

소수 구하기
소수는 에라토스테네스의 체로 구해줬다.

소수의 연속합 개수 구하기
이 과정은 투포인터로 풀어줬다. 두 포인터를 모두 시작점에 두고, 목표값인 n과 비교하며 포인터를 옮겨줬다.
left번째 값부터 right번째 값을 구하는 것이기 때문에, right 포인터를 옮길때는 옮긴 뒤 sum에 더해주고, left값은 sum에서 뺀 뒤 포인터를 옮겨주면 된다.

만약 두 값이 같다면 ans값을 1 증가 시킨 뒤, 포인터 둘 다 옮겨주면 된다.

🔵 Ref