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

 

 

일단, 못풀었다.

너무 어려워!

 

 

배열에서 3개의 요소를 골라서 합하고, 그 값이 자기 자신과 1로 나눴을 때를 제외하곤 모두 나머지가 있어야 한다. 

찾아보니 재귀함수, 순열, 조합의 개념이 나온다. 

 

아래에 재귀함수의 개념을 정리해보고, 일단은 답 코드를 본다.

 

 

 

문제설명

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

제한사항

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

입출력 예시

numsresult

[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예시 설명

입출력 예 #1

[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2

[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

문제풀이

function solution(nums) {
    let answer = 0;
    const len = nums.length;
    
    for (let i=0; i<len; i++) { //배열 안에서 서로다른 3개의 수를 더하기
        for (let j=i+1; j<len; j++) {
            for (let k=j+1; k<len; k++) {
                let sum = nums[i] + nums[j] + nums[k];
 
                if (isPrime(sum)) { //소수라면 정답 count++
                    answer++;
                }
            }
        }
    }
 
    function isPrime(sum) {
        if (sum < 2) return true;
        for (let i=2; i<sum; i++) { //1외에 숫자 하나라도 나누어떨어지면 소수탈락
            if (sum % i == 0) return false;
        }
        return true;
    }
 
    return answer;
}

• for문 3개를 반복해주며 숫자들에 접근해서 소수 판별을 한다
• Math.sqrt() 메소드를 사용하여 소수 판별 시 제곱근 만큼만 판별한다

 

사용한 메소드

Math.sqrt(x)

• 주어진 숫자의 제곱근. 숫자가 음수이면 NaN 이 반환된다
• x 값 이 음수이면 Math.sqrt() 는 NaN 을 반환한다.

 

 

 

 

---

재귀함수

함수가 자신을 다시 호출하는 구조로 만들어진 함수이다. 재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복을 하게된다. 재귀함수로 작성이 되는 코드는 반복문으로도 작성할 수 있다.

 

(예제 1) 1부터 100의 합 구하기

function f(n) {
    if (n <= 1) {
       return 1 // 종료 조건
    }
    return n + f(n-1) // 재귀함수
}
console.log(f(100)) //5050
// 재귀함수
// 순번   f(n)   n      return       최종
// 1   f(100)  100  100 + f(99)  100+99+98+97+96+95+94..+2+1   
// 2   f(99)   99   99 + f(98)   99+98+97+96+95+94..+2+1 
// 3   f(98)   98   98 + f(97)   98+97+96+95+94..+2+1 
// 4   f(97)   97   97 + f(96)   97+96+95+94..+2+1 
// ...
// 2   f(2)    2    2 + f(1)    2+1
// 1  f(1)    1    1 // return값이 자기 자신을 호출하지 않는 상황

여기서 사용된 for문 조건은 1부터 순회한다. 재귀함수의 경우는 100부터 순회한 다음 호출 스택에 쌓여 있는 값을 처리해 나가게 되는데 스택은 LIFO방식이기 때문에 이때 스택에 제일 마지막으로 반환된 1부터 100까지 순차적으로 더해서 값을 반환하게 된다. 곱하기 방식도 위와 같다.

 

(예제 2) 문자열 뒤집기

function strReverse(str) {
    if (str.length == 1) {
        return str //종료 조건
    }
    return str[str.length-1] + strReverse(str.slice(0, str.length-1)); // 순서 더하는 순서 바꾸면 정순
}
console.log(strReverse('bakjeongin')); //nignoejkab

// strReverse(str)          str[str.length-1] + strReverse(str.slice(0, str.length-1)
// strReverse('bakjeongin') str[9] + strReverse(str.slice(0, 9) / 'n' + 'ignoejkab' -> nignoejkab
// strReverse('bakjeongi') str[8] + strReverse(str.slice(0, 8) / 'i' + 'gnoejkab' -> ignoejkab
// strReverse('bakjeong') str[7] + strReverse(str.slice(0, 7) / 'g' + 'noejkab' -> gnoejkab
// strReverse('bakjeon') str[6] + strReverse(str.slice(0, 6) / 'n' + 'oejkab' -> noejkab
// strReverse('bakjeo') str[5] + strReverse(str.slice(0, 5) / 'o' + 'ejkab' -> oejkab
// strReverse('bakje') str[4] + strReverse(str.slice(0, 4) / 'e' + 'jkab' -> ejkab
// strReverse('bakj') str[3] + strReverse(str.slice(0, 3) / 'j' + 'kab' -> jkab
// strReverse('bak') str[2] + strReverse(str.slice(0, 2) / 'k' + 'ab' -> kab
// strReverse('ba') str[1] + strReverse(str.slice(0, 1) / 'a' + 'b' -> ab 
// strReverse('b') str[0] + strReverse(str.slice(0, 0) / 'b'

 

재귀함수는 메모리를 많이 차지하고 성능이 반복문에 비해 느리다. 함수를 반복적으로 호출하므로, 스택 메모리가 커지고, 호출하는 횟수가 많아지면 스택오버플로우가 발생할 수 있다. 상황에 따라 적절하게 사용하도록 하자.

 

 

 

 

 

참고

[Programmers] 소수 만들기 / JavaScript

[Javascript] 재귀함수

자바스크립트 개발자라면 알아야 할 33가지 개념 #23 자바스크립트 : 자바스크립트 재귀(Recursion) 이해하기