Dony :)

FE로 성장 중 🌱

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/12977

답안

나의 풀이

function solution(nums) {
  const sums = [];

  for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        sums.push(nums[i] + nums[j] + nums[k]);
      }
    }
  }

  let answer = sums.length;
  for (const sum of sums) {
    if (sum % 2 === 0) {
      answer--;
      continue;
    }

    for (let divisor = 3; divisor <= Math.sqrt(sum); divisor += 2) {
      if (sum % divisor === 0) {
        answer--;
        break;
      }
    }
  }

  return answer;
}

시간복잡도: O(N3)

  1. 3자리를 고르기 위해 i, j, k 3중 반복문을 돈다.
  2. 두번째 자리는 첫번째 자리를 제외하고 선택할 수 있고 세번째 자리도 첫번쨰, 두번째 자리를 제외하고 선택할 수 있다. 따라서 반복문의 조건을 j = i + 1, k = j + 1로 설정한다.
  3. 각 세자리수를 더해 sum 배열에 push 한다.
  4. answer은 sum의 길이로 초기값을 정해놓고 소수가 아닌 경우를 찾을 때마다 -1을 해준다.
  5. ‘에라토스테네스의 체’의 공식을 사용하여 sum의 제곱근까지만 반복문을 돌면서 짝수인 경우는 제외해야하므로 +2씩 건너뛰어 소수를 찾는다.

참고