[Javascript] 프로그래머스 소수 찾기

문제

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

코딩테스트 연습 - 소수 찾기

한 자리 숫자가 적힌 종이 조각이 흩어져 있을 때, 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내는 문제다.

 

지금까지 알려진 것 중에 가장 빠른 방법이라고 하는 에라토스테네스의 체를 사용해 소수를 판별하였다. 이름과 같이 소수가 아닌 것들을 체로 걸러가면서 확인하는 방법이다. 예를 들어 1부터 100까지의 수가 있다고 가정한다면, 1은 소수가 아니므로 제거, 2는 소수이므로 저장, 저장된 2의 배수(4, 6, 8, 10...)는 소수가 아니므로 제거, 제거되지 않은 3은 소수이므로 저장, 3의 배수(9, 15, 21, 27...  6, 12 등의 숫자가 포함되지 않는 이유는 이전 소수 2의 배수를 처리할 때 제거되었기 때문이다)는 소수가 아니므로 제거... 이런 식으로 진행하는 방법이다. 시간 복잡도는 소수를 찾을 때마다 그에 대한 배수는 제거 되므로 O(log n)이 걸리지 않을까 생각한다.

 

출처: https://ko.wikipedia.org/wiki/에라토스테네스의_체

풀이 방법

1. 파라미터로 받은 종이 조각을 갖고 만들 수 있는 최솟값, 최댓값을 구한다.

2. 최솟값부터 최댓값까지의 범위 내에서 숫자를 1씩 증가시킨다

3. 해당 숫자가 파라미터의 조합이라면 소수 판별을 진행한다.

   • 소수인 경우, 해당 숫자의 배수(해당 숫자는 제외)를 모두 nonPrimeObj 객체에 저장한다.

   • 소수가 아닌 경우, 해당 숫자만 nonPrimeObj 객체에 저장한다

   • 숫자를 판별할 때, nonPrimeObj에 저장되지 않은 숫자만 확인하기 때문에 시간을 단축시킬 수 있다.

4. 소수로 판별되면 count를 1 증가시킨다.

// 내가 작성한 코드
  function solution(numbers) {
      let count = 0;
      let nums = numbers.split('').sort((a, b) => b - a);
      // numbers를 조합해 만들 수 있는 최소값
      const min = nums[nums.length - 1];
      // numbers를 조합해 만들 수 있는 최대값
      const max = nums.reduce((a, b) => a + b);
      // numbers가 1자리 수인 경우, 바로 판별해서 개수 반환
      if(numbers.length === 1){
          if(checkPrime(Number(numbers))){
              return 1;
          }
          return 0;
      }
      // 소수 판별 함수
      function checkPrime(num){
          if(num <= 1){
              return false;
          }else if (num % 2 === 0){
              if(num === 2){
                  return true;
              }
              return false;
          }else if (Math.sqrt(num) % 1 === 0){
              return false;
          }else {
              for(let i = 3; i < Math.sqrt(num); i = i + 2){
                  if (num % i === 0) return false;
              }
              return true;
          }
      }
      // start(최소값) ~ end(최대값) 까지 소수 판별
      function findPrimeNum(start, end){
          // 소수가 아닌 숫자를 저장할 객체
          let nonPrimeObj = {};
          for(let i = start; i <= end; i++){
             if(!nonPrimeObj[i]){ 
                  let check = [];
                  let str = i + '';
                  check = check.concat(nums);
                  // numbers로 조합할 수 있는 숫자인지 아닌지 확인
                  for(let j = 0; j < str.length; j++){
                      if(check.indexOf(str[j]) !== -1){
                          check.splice(check.indexOf(str[j]), 1);
                      }else{
                          break;
                      }
                  }
                  // numbers로 조합할 수 있는 숫자이고
                  if(check.length + str.length === numbers.length){
                      // 만약 소수라면
                      if(checkPrime(i)){
                          // 해당 숫자의 배수는 모두 nonPrimeObj에 저장하고
                          for(let np = i * 2; np <= end - i; np = np + i){
                              nonPrimeObj[np] = true;
                          }
                          // count + 1을 해준다
                          count = count + 1;
                      // 만약 소수가 아니라면
                      } else {
                          // 해당 숫자만 nonPrimeObj에 저장한다
                          nonPrimeObj[i] = true;
                      }
                  } 
              }
          }
      }
      findPrimeNum(Number(min), Number(max));
      // 결과 반환
      return count;
  }

 

테스트 케이스

"7843" 12

"333" 1

"0" 0

"1" 0

"2" 1

"1276543" 1336

"100" 0

"999999" 0

 

 

 

 

---

참고 자료

• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4