[프로그래머스] lv1. 소수 만들기

 

문제

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

코딩테스트 연습 - 소수 만들기

풀이

1. 함수(solution)의 인자(nums)로 들어온 배열 값 중에 3개의 값을 조합으로 찾는다.

2. 3개로 조합된 값들을 합산한 값이 소수이면 answer값을 1증가 시킨다.

3. 2번을 완료하면 answer를 리턴한다.

코드

<script>
function solution(nums) {
  let answer = 0, arr=[];

  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++) {
        arr.push(nums[i] + nums[j] + nums[k])
      }
    }
  }
  for (let x of arr) if (isPrime(x)) answer++;
  return answer;
}

function isPrime(num) {
  for (let i = 2; i*i <= num ; i++) if (num % i === 0) return false;
  return true;
}
</script>

 

느낀점

이번 문제의 목표는 아래와 같다

1. 배열인자들 중에 3개 값을 조합으로 구하는 것

2. 소수를 판별하는 방법

 

lv1 이라서 3개 값만 조합으로 찾아라 했지, 만약에 랜덤 개수의 묶음으로 조합을 찾아라고 했으면, 더 어려운 문제가 되었을 것이다.

그렇게 된다면, 아래 참고 블로그에서 보여주듯 재귀를 이용해서 조합된 값을 구해야한다.

재귀를 이용한 조합알고리즘도 공부해야겠다는 생각이 들었다.

 

소수판별은 반복문을 돌때 초기값은 2,  종료조건은 Math.sqrt(인자값) 이하일 때 돌면 된다는 것을 알게 되었다.

그럼 for (let i = 2; i < Math.sqrt(num); i++) 이 되는데, 더 빠른 연산을 하기 위해서

for (let i = 2; i * i < num; i++) 을 하는게 더 좋다는 것도 알게되었다.

 

참고

https://jun-choi-4928.medium.com/javascript로-순열과-조합-알고리즘-구현하기-21df4b536349

JavaScript로 순열과 조합 알고리즘 구현하기

https://mine-it-record.tistory.com/508

[알고리즘] 조합, 순열, 중복순열 - 경우의 수 찾기 by javascript (ft. 모든 경우의 수)