[TIL] 24.06.11 백준 6588번 js

내가 푼 문제 📖

 

내가 작성한 코드 💻

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : __dirname+"/input.txt")
  .toString()
  .trim()
  .split('\n')
  .map(Number)
const size = input.pop();
const numbers = Array(1000000).fill(true); 
const sosu = [];
numbers[0] = false
numbers[1] = false

for(let j=2; j<=Math.sqrt(1000000); j++){
  if(!numbers[j]) continue;

  sosu.push(j)
  for(let k = j * 2; k <= 1000000; k += j){
    numbers[k] = false;
  }
}

const results = input.map(num => {
  const low = sosu.find(su => numbers[num - su])
  if(low){
    let high = num - low

    return `${num} = ${low} + ${high}`;
  }
  return `Goldbach's conjecture is wrong.`
})

console.log(results.join('\n'))

 

어려웠던 점 ❓

1. 에라토스테네스의 체

for(let j=2; j<=Math.sqrt(1000000); j++){
  if(!numbers[j]) continue;

  sosu.push(j)
  for(let k = j * 2; k <= 1000000; k += j){
    numbers[k] = false;
  }
}

정수의 범위가 100만까지여서 for문으로 소수를 구하게 되면 메모리 초과가 뜨는 불상사가 발생하기 때문에 에라토스테네스의 체 알고리즘을 이용했어야 했다. 예전에 잠깐 스쳐 지나가듯 공부한 적이 있어서 문제 푸는데 도움이 될 줄 알았지만,,, 다 까먹어 버렸다.🤗

 

2. 조합

const combination = (arr ,selectNumber, targetNumber) => {
  const results = [];

  if(selectNumber === 1) return arr.map(el => [el])

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index+1)
    const getCombination = combination(rest, selectNumber-1)
    results.push(...getCombination.map(com => {
      if(parseInt(...com) + parseInt(fixed) === targetNumber) return [fixed, ...com]
      return 0
    }))
  })

  return results;
}

어찌어찌 소수를 구하긴 했지만 "(N = A+B) A와 B는 홀수인 소수여야 했고 N을 만들 수 있는 방법이 여러 가지라면, B-A가 가장 큰 것을 출력한다."라는 조건이 있었기 때문에 내가 생각해 낸 방법은 다름 아닌 조합이었다!

,,,,,

 

하지만 메모리 초과ㅠㅠ

깨달은 점 ❕

이틀 동안 고민했는데도 문제를 풀지 못해서 정답 참고를 해 도움을 얻었다. 막상 정답을 보면 그렇게 어려운 문제가 아니었다. 근데 나는 왜 이 문제를 못 풀고 있었을까??

 

회고 🧐

잠깐씩 스쳐 지나가는 알고리즘들이 점점 중요하다는 생각이 든다.

---

 

출처 🏷️

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전