링크
https://school.programmers.co.kr/learn/courses/30/lessons/12977
문제
숫자들의 배열이 주어질 때, 배열 안의 3개의 수를 뽑아서 더했을 때 그 수가 소수가 나오는 경우의 수를 구하라.
예제로 이해
[1, 2, 7, 6, 4]
다음과 같은 배열이 주어질 때 세 개의 숫자를 뽑는 방법과 그 수를 더했을 때 나오는 값은 다음과 같다.
1 2 7 => 10
1 2 6 => 9
1 2 4 => 7
1 7 6 => 14
1 7 4 => 12
1 6 4 => 11
2 7 6 => 15
2 7 4 => 13
2 6 4 => 12
7 6 4 => 17
더해서 만들어진 수 중에서 소수는 7, 11, 13, 17 이므로 소수가 나올 수 있는 경우의 수는 4이다.
코드
function solution(nums) {
let arr = []
let count = 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++) {
arr.push(nums[i] + nums[j] + nums[k])
}
}
}
arr.map(el => {
for(let i = 2; i <= Math.floor(Math.sqrt(el)); i++) {
if(el % i === 0) {
return
}
}
count++
})
return count
}코드 풀이
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++) {
arr.push(nums[i] + nums[j] + nums[k])
}
}
}위의 3중 for문은 겹치지 않게 3개의 숫자를 뽑아내는 3중 반복문이다. 뽑아낸 3개의 수를 더해서 새로운 배열에 저장한다.
arr.map(el => {
for(let i = 2; i <= Math.floor(Math.sqrt(el)); i++) {
if(el % i === 0) {
return
}
}
count++
})뽑아낸 수가 소수인지 판별하는 반복문이다. 더한 값을 저장해놓은 배열에서 하나하나씩 뽑아서 소수인지 비교하기 위해서 map 함수를 사용한다.
map 함수의 내부에는 그 숫자가 소수인지 판별하는 식이 있는데 소수를 판별하는 방법에는 크게 3가지가 있다.
-
만약 판별하고자 하는 숫자가 15라면 2부터 14까지 15와 나머지 연산을 했을 때 0이 나오는 숫자가 있다면 그 15는 소수가 아니다.
-
어떤 수의 약수는 자기 자신의 절반보다 클 수 없기 때문에 위의 1번과 같은 과정을 (자신 - 1) 이 아닌 (자신 / 2 - 1) 까지 연산을 실행한다.
-
소수를 판별할 때는 굳이 절반이 아닌 제곱근까지만 반복을 실행해도 충분하다. 따라서 1번과 같은 과정을 (Math.sqrt(자신) - 1) 까지 연산을 실행한다.
세가지 방법 모두 소수를 판별할 수 있는 방법이지만, 숫자가 매우 크다면 반복문을 돌리는 시간도 오래 걸리기 때문에 시간 복잡도가 가장 짧은 3번 방법에 대해서 for문을 실행하였다.
반복문을 실행하면서 el의 제곱근까지만 반복을 진행하고, 반복문 안에는 제곱근까지 1씩 증가시킨 수에 나머지 연산을 진행해서 0이 나온다면 return을 실행하여 소수 count에 포함시키지 않았다. 만약 반복문을 끝마칠때까지 return이 실행되지 않는다면 그 숫자에 대해 나누어 떨어지는 숫자가 없다는 의미이므로 소수를 세는 count에 + 1을 진행해서 소수가 나오는 경우의 수를 구해주었다.
