프로그래머스 소수 찾기 자바스크립트

문제 링크

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

프로그래머스

 

문제 풀이를 위해 생각한 것

1. 순서가 상관 있으며, 숫자 문자열의 각 원소로 만들 수 있는 모든 수를 구한다. -> 순열
2. 구한 순열을 모두 배열에 추가한 뒤, Set 자료구조로 중복을 제거한다.
3. 중복을 제거하고 남은 모든 수에 대해 소수 판별 알고리즘을 적용한다.

 

사용한 자료구조 / 알고리즘

집합 자료구조 / 소수 판별 / 순열 / 재귀

 

풀이 코드

const getPermutations = function(arr, numberSelect) {
    const result = []
    if (numberSelect === 1) return arr.map(el => [el])
    
    arr.forEach((fixed, index, origin) => {
        const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
        const permutations = getPermutations(rest, numberSelect - 1)
        const permutation = permutations.map((p) => [fixed, ...p])
        result.push(...permutation)
    });
    
    return result
}

const isPrime = function(n) {
    
    if(n === 0 || n === 1) return false
    
    for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
        if (n % i === 0) return false
    }
    return true
}


function solution(numbers) {
    let answer = 0;
    
    const nArr = numbers.split('')
    let ansArr = []
    
    // 1부터 nArr의 길이 만큼 반복하며, 순열 도출
    for (let i = 1; i <= nArr.length; i++) {
        let pArr = getPermutations(nArr, i)
        
        // 도출한 순열을 Number로 바꾸어 결과 배열에 추가
        pArr.forEach(el => {
            const num = Number(el.toString().replace(/,/g, ''))
            ansArr.push(num)
        })
    }
    
    // 중복 제거
    const setArr = new Set(ansArr)
    ansArr = [...setArr]
    
    // 소수 판별
    ansArr.forEach(el => {
        if (isPrime(el)) {
            answer++
        }
    })
    
    return answer;
}

 

시간 복잡도 분석

O(N!).

순열의 시간 복잡도 O(N!)이 본 알고리즘에서 가장 큰 시간 복잡도를 가지므로, 시간 복잡도는 O(N!)이다.

 

문제에서 중요한 부분

1. 소수 판별 알고리즘을 기본으로, 순열과 Set 자료구조를 활용한 중복 제거 아이디어를 떠올릴 수 있어야 했다.
2. 소수 판별 알고리즘에서, 2부터 n의 제곱근 까지 약수가 없으면 n의 제곱근 이후의 숫자에서도 본인을 제외한 약수가 없음을 의미한다.
3. 순열 알고리즘에서, 현재 인덱스 원소를 제외한 모든 원소에 대해 재귀적으로 순열을 구하고, 이를 현재 인덱스 원소와 결합함으로써 순열을 구할 수 있었다.