[프로그래머스] 소수 만들기 (Level 1)

문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
 

• 제한사항
  • nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
  • nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
     

나의 풀이

1. 첫 번째 풀이

  function solution(nums) {

      let answer = 0;

      for(let i = 0; i < nums.length; i++) {
          for(let j = i + 1; j < nums.length; j++) {
              for (let k = j + 1; k < nums.length; k++) {

                  let sum = nums[i] + nums[j] + nums[k];

                  // 더한 수가 소수인지 확인
                  for(let l = 2; l < sum; l++) {

                      //  소수x -> continue;
                      if (sum % l === 0) break;

                       //  소수 -> answer + 1
                      else if (l === sum -1) answer+= 1;
                  }
              }
          }
      }
      return answer;
  }

 
중첩문을 사용해 경우의 수의 구조를 만들고
중첩문 안에 소수 판별 함수를 넣었더니 실행 시간이 오래 걸렸다.
통과는 했지만 수정이 필요한 코드.
 

• 정확도 테스트 결과

  

  
   

2. 1차 수정

  function solution(nums) {

      let answer = 0;

      for(let i = 0; i < nums.length; i++) {
          for(let j = i + 1; j < nums.length; j++) {
              for (let k = j + 1; k < nums.length; k++) {

                  let sum = nums[i] + nums[j] + nums[k];

                  // 더한 수가 소수인지 확인
                  if(isPrime(sum)) answer += 1;
                  }
              }
          }
          return answer;

      function isPrime(n) { // 소수 판별 함수

          for(let i = 2; i < n; i++) {

              if(n % i === 0) return false;
          }
          return true;
      }
  }

 
소수 판별 함수를 바깥으로 빼서 boolean을 반환하게 했다.
실행 시간이 줄어들었다.
 

• 정확도 테스트 결과

  

  
   

3. 최종 모범 답안

  function solution(nums) {

      let answer = 0;

      for(let i = 0; i < nums.length; i++) {
          for(let j = i + 1; j < nums.length; j++) {
              for (let k = j + 1; k < nums.length; k++) {

                  let sum = nums[i] + nums[j] + nums[k];

                  // 소수 판별 함수
                  if(isPrime(sum)) answer += 1;
                  }
              }
          }
          return answer;

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

 
소수를 판별할 때, 굳이 정수 끝까지 모두 나눠볼 필요가 없었다.
Math.sqrt()를 이용해서 정수의 제곱근까지만 나눠보면 판별 가능하다.
실행 시간이 많이 줄었고, 이게 모범 답안인 것 같다.
 

• 정확도 테스트 결과

  

  
   

참고

gurtn.tistory.com/101