[21번] [중급] 소수 만들기

문제

프로그래머스

 

나의 답

[pseudo code] => 이 방법은 정확성은 맞지만, 런타임 에러로 통과를 못함
1. for 3중첩문을 사용해 세자리 숫자의 합으로 만들어지는 모든 숫자를  sumArr에 담는다
2. sumArr의 숫자가 소수인지 판별해줄 재귀함수
    - 2 ~ Math.sqrt(숫자)까지 factor 배열에 담아준다. 이때, 배열에는 2를 제외한 모든 짝수를 제거
    - factor 안에 담긴 값이 factor 안에 담긴 다른 값의 배수라면 이를 삭제
    - sumArr의 숫자를 모든 factor 값으로 나눴을 때 나눠 떨어지는 것이 있다면 해당 숫자는 소수가 아니므로 다음 숫자로 넘어감
    - factor의 모든 값으로 나눈 나머지가 0이 아니라면, 해당 숫자는 prime이므로, count++
3. return count

 

function solution(nums) {
  let count = 0,
    prime = [];
  let sumArr = [];

  // 세자리 숫자의 합으로 만들어지는 모든 숫자를  sumArr에 담는다
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let h = j + 1; h < nums.length; h++) {
        let sum = nums[i] + nums[j] + nums[h];
        sumArr.push(sum);
      }
    }
  }

  // sumArr의 숫자가 소수인지 판별해줄 재귀함수
  function createFactor(p) {
    // 2부터 Math.sqrt(sumArr[p])를 factor 배열에 추가한다. 이때, 2보다 큰 짝수는 넣지 않는다.
    if (p < sumArr.length) {
      let factor = [];
      for (let i = 2; i <= Math.sqrt(sumArr[p]); i++) {
        if (i === 2 || i % 2 !== 0) {
          factor.push(i);
        }
      }
      console.log("filter 전: ", factor);

      //factor 안 값이 factor 안에 값으로 나누어 떨어지는 것이 있다면 삭제
      for (let i = factor.length - 1; i > 0; i--) {
        for (let j = 1; j < factor.length - 1; j++) {
          if (factor[i] !== factor[j] && factor[i] % factor[j] === 0) {
            factor.splice(i, 1);
          }
        }
      }
      console.log("filter 후: ", factor);

      // sumArr[p]의 factor 값을 이용해 sumArr[p]가 prime number인지 확인 -> prime이면 count++
      if (factor.length !== 0) {
        console.log("sum 값:", sumArr[p], factor);
        for (let i = 0; i < factor.length; i++) {
          //만약 검사 중 한번이라도 나머지 값이 0이되면 그 숫자는 소수가 아니므로, 함수를 종료하고 p값을 올려 재귀호출
          if (sumArr[p] % factor[i] === 0) {
            p++;
            return createFactor(p);
          }
        }
        // factor의 요소로 숫자를 검사하는 for문이 종료 된 후에 (즉, 모든 factor로 다 나눴는데, 나머지 값이 0이 나오지 않았다면)는 해당 숫자가 소수이므로, count를 올리고, prime 배열에 해당 값을 추가한다.
        count++;
        prime.push(sumArr[p]);
        // 이후 다음 숫자를 검사하기 위해 재귀호출
        p++;
        return createFactor(p);
      }
    } else {
      return count;
    }
  }

  createFactor(0);

  return count;
}

console.log(solution([1, 2, 3, 4]));
console.log(solution([1, 2, 7, 6, 4]));
console.log(solution([10, 77, 89, 145, 111, 131, 2, 1]));

 

 

[ pseudo code version2]
위와 같은 로직이지만, 런타임을 줄이기 위해 재귀를 사용하지 않았고, prim 검사도 간결하게 함(factor를 따로 검증하지 않고 단순히 2 ~ Math.sqrt(num)으로 진행)

// isPrime 검사를 단독 function으로 만들고, for loop를 한번만 써서 간단하게 만들기
function solution(nums) {
  let count = 0;
  // 세자리 숫자의 합으로 만들어지는 모든 숫자를  sumArr에 담는다
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let h = j + 1; h < nums.length; h++) {
        if (isPrime(nums[i] + nums[j] + nums[h])) {
          count++;
        }
      }
    }
  }
  return count;
}

function isPrime(sum) {
  for (let i = 2; i <= Math.sqrt(sum); i++) {
    if (sum % i === 0) return false;
  }
  return true;
}

 

이 문제는 푸는데 한 3시간정도 걸린것 같다ㅠㅠ

너무 엄밀하게 하려고 하다가 결국 런타임 에러...

이 문제를 통해서 프로그래밍은 너무 엄밀하게 하기보다 효율성을 같이 잡아야 한다는 것이 더욱 더 확 느껴진다.