프로그래머스 - Level 1. 소수 만들기 / JavaScript (js)

문제설명

문제분석

주어진 숫자에 중복은 없고, 3개를 골라서 더했을 때 소수가 되는 경우를 세아리면 되는 간단한 문제입니다.

• 소수를 판별하는 함수를 구현한다.
• 배열의 요소 중 3개를 선택하는 로직을 구현한다.

문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다.

이해하기 쉽게 코드작성하기

function solution(nums) {
    let answer = 0;
    const arr = [];
    
    // nums 배열에서 3가지 요소를 임시 배열 arr에 담고, 요소의 합이 소수인지 검사
    (function recursion(nums, idx) {
        if (arr.length === 3) {
            if (isPrime(arr.reduce((a,c)=>a+c),0)) {
                answer++;
                return;
            }
        }
        for (let i = idx; i < nums.length; i++) {
            arr.push(nums[i]);
            recursion(nums, i+1);
            arr.pop();
        }
    })(nums, 0);
    
    return answer;
}

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

코드 설명

nums를 순회하며 순차적으로 하나씩 요소를 꺼내고, 요소의 합이 3개가 되었을 때 소수인지 판별합니다. 로직은 이렇게 구현하면 되는데, 이렇게 구현했을 때는 큰 문제가 있습니다.

시간초과가 뜬다는 것이지요. 이런 경우에는 두 가지 부분으로 나눠 리팩토링해볼 수 있습니다.

1. 재귀문을 반복문으로 변경한다.
2. 소수 판별할 때 memoization을 활용한다.

먼저 재귀문을 반복문으로 변경하는 것으로 훨씬 빠르게 코드를 실행할 수 있습니다. 비록 위 코드에서 재귀문은 depth가 3밖에 되지 않지만, 리팩토링된 코드로 테스트한 결과를 보면 유의미한 차이를 확인할 수 있습니다.

 

두번째 memoization을 활용한다는 건, 말 그대로 잠시 기록해두겠다는 의미입니다. 상대적으로 메모리는 더 소모하겠지만, 훨씬 빠르게 데이터에 엑세스할 수 있기때문에 소수판별이 훨씬 빨라질 것이기 때문입니다. 위 코드를 다음처럼 변경합니다.

function solution(nums) {
    let answer = 0;
    const memo = {};
    
    // 반복문으로 변경
    for(let first = 0; first < nums.length - 2; first++) {
        for(let second = first + 1; second < nums.length - 1; second++ ) {
            for(let third = second + 1; third < nums.length; third++) {
                const sum = nums[first] + nums[second] + nums[third];
                // memo 객체에 기록돼있는지 확인
                if(memo[sum] || isPrime(sum)) {
                    answer += 1;
                    if(memo[sum] === undefined) {
                        memo[sum] = true;
                    }
                }
            }
        }
    }
    
    return answer;
}

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

테스트 1을 보면, 이전 재귀문에는 2180 ms가 소요되었지만, 반복문에서는 0.57ms 가 소요된 걸 알 수 있습니다. 물론 반복문만 적용한 것과는 달리, memoization을 적용했기에 더 빨라졌습니다. 다음은 memoization을 사용하지 않은 경우입니다. 모두 통과하지만 미세하게 더 빠릅니다. 만약 nums에 들어있는 숫자의 개수가 더 많아지거나 nums의 각 원소 범위가 더 커진다면 유의미한 결과를 보여줄 겁니다.

앞서 언급한 것처럼 재귀문의 depth가 3밖에 되지 않기때문에 memoization으로 인해 빨라진 것이라 생각할 수도 있습니다. 그러나 재귀문에 memoization을 적용한 경우, 다음처럼 여전히 시간 초과가 나타납니다.

만약 실무에서 prime을 판별해야 한다면, db나 캐시로 소수를 저장해두고 memo를 확인하는 형태를 취했을 것 같습니다.