[JS] 9020

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : './data.txt';

const input = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((x) => Number(x));

function solve(input) {
  let caseCount = input.shift();

  for (let number of input) {
    let arr = [...new Array(number + 1).keys()];
    for (let i = 2; i <= Math.sqrt(number); i++) {
      if (arr[i]) {
        for (let j = i * i; j <= number; j += i) {
          arr[j] = false;
        }
      }
    }
    arr = arr.filter((x) => x >= 2);

    let a, b;

    // 이중 반복문으로 인해 시간초과

    // for (let i of arr) {
    //   for (let j of arr.filter((x) => x >= i)) {
    //     if (i + j === number) {
    //       a = i;
    //       b = j;
    //       break;
    //     }
    //   }
    // }

    // 다음과 같이 반복문 수정

    for (let i of arr) {
      let j = number - i;
      if (arr.includes(j) && i <= j) {
        a = i;
        b = j;
      }
    }

    console.log(`${a} ${b}`);
  }
}

solve(input);

백준

마찬가지로 에라토스테네스의 체를 활용하여 해당 숫자보다 작거나 같은 소수 배열을 만들었다.
이후 그 배열 내의 합이 주어진 숫자와 같은 경우를 찾았다.
처음엔 이중반복문을 이용하여 단순하게 모두 탐색하였다가 '시간 초과'가 나와
두번째 반복문에서 i보다 크거나 같은 수를 필터한 배열을 해주고 break도 해주었지만 역시나 이중반복문 자체가 시간복잡도가 너무 커서 시간 초과...
고민 중에 반복문을 한번 쓰고 mdn에서 배열의 함수 includes를 활용하여 풀 수 있었다.
확실히 알고리즘 문제는 성취감이 큰 것 같다. :) 캬~