[프로그래머스] 소수 찾기 - 완전탐색 (JS)

프로그래머스 알고리즘 고득점 kit - 완전 탐색(=brute force) 문제

문제

처음 접근 시도

// 1) split로 numbers을 배열 만들기
// 2) numbers로 만들 수 있는 모든 숫자 구하는 로직
//      2.1) 맨앞이 0인 경우 제외 -> continue 사용 
//      2.2) 1도 제외
//      2.3) numbers.length만큼 반복 (한 자리 수, 두 자리 수...)
// 3) 소수인지 판별하는 로직
//      3.1) 2부터 9까지 나눠서 나머지가 1이상 나오는 경우 -> 소수

function solution(numbers) {
    var answer = 0;
    numbers = numbers.split('');
    console.log(numbers.length);
    for (int i = 1; i <= numbers.length; i*10){
       
    }
    return answer;
}

나름 처음부터 설계 고민하고 풀려고 하다가 숫자를 만들 수 있는 모든 경우의 수를 구하는 방법에서 막혔다. 그래서 나름 패턴을 찾아보려고 직접 숫자가 2개,3개,4개 인 경우를 계산해봤는데…쉽지 않았다

 

그래서 풀이를 보니 Set()를 사용하면 된다고 한다

 

그리고 parseInt를 쓰면 앞에 0인 경우를 없애준다고도 알게되었다. 원래는 if문으로 첫자리가 0이면 continue해서 넘기려했는데 이렇게 손쉬운 방법이…

풀이

function solution(numbers) {
    // 1. 문자열을 배열로 분리
    let digits = numbers.split('');
    let uniqueNumbers = new Set();
    
    // 2. 재귀 함수를 이용해 가능한 모든 순열(숫자 조합) 생성
    function generatePermutation(current, remaining) {
        if (current !== "") {
            uniqueNumbers.add(parseInt(current)); // parseInt가 앞의 0을 제거해줌
        }
        for (let i = 0; i < remaining.length; i++) {
            // 남은 숫자 중 하나를 선택해 current에 추가하고, 나머지 배열로 재귀 호출
            generatePermutation(current + remaining[i], remaining.slice(0, i).concat(remaining.slice(i + 1)));
        }
    }
    
    generatePermutation("", digits);
    
    // 3. 소수 판별 함수
    function isPrime(n) {
        if (n < 2) return false; // 0과 1은 소수가 아님
        for (let i = 2; i <= Math.sqrt(n); i++) {
            if (n % i === 0) return false;
        }
        return true;
    }
    
    // 4. 고유 숫자들 중 소수 개수를 계산
    let count = 0;
    uniqueNumbers.forEach(num => {
        if (isPrime(num)) count++;
    });
    
    return count;
}

 

숫자 조각 분리

• 주어진 문자열을 split('')을 사용해 개별 숫자(문자) 배열로 만들기

모든 숫자 조합(순열) 생성

• 재귀 함수를 이용해 한 자리, 두 자리, ... 최대 전체 길이의 모든 순열 만들기
  • 현재 조합이 빈 문자열이 아닐 때마다 정수로 변환하여 Set에 추가하면, 중복된 숫자는 자동으로 걸러짐
  • 문자열 앞에 '0'이 붙은 경우라도 parseInt를 사용하면 자동으로 제거되므로(예: "011" → 11), 별도의 처리가 필요 X

소수 판별

• 생성된 각 숫자에 대해 2 이상의 수부터 √n까지 나누어 떨어지는지 확인하는 소수 판별 함수를 구현합니다.
  • 0과 1은 소수가 아니므로 판별 과정에서 제외

소수 개수 반환

• Set에 저장된 고유 숫자들 중 소수에 해당하는 숫자의 개수를 계산하여 반환

배운점

- 재귀함수 사용하기

: 재귀함수라는게 뭔지는 알고 있었지만 이걸 이 문제에 이용할 생각을 못했었다. 재귀 함수를 이용하면 코드가 더 단순해지고 가독성이 좋아질 수 있다.

 

- Set()

: 중복되지 않는 유일한 값들만 저장할 수 있는 컬렉션이다. 즉 배열과는 달리 같은 값을 넣어도 한 번만 저장되기에, 데이터가 중복되는것을 맊을 수 있다. 그리고 삽입된 순서도 유지하기에 for문과 같은 반복문을 통해 순서대로 값을 사용할 수 있다.

 

- parseInt()

: 문자열 숫자를 정수로 변환해준다. 즉, 만약 숫자 앞에 0이 있으면 제거해준다 ex) "011" -> 11