프로그래머스 - 소수 찾기

<문제>

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

프로그래머스

 

 

<문제 핵심>

1. 완전 탐색

개념: 모든 경우의 수를 시도하는 방법(if문, 반복문을 사용하며 모든 경우를 확인)

 

✅ 경우의 수가 많을 수록 실행 시간이 늘어나기 때문에 입력값의 범위가 적을 때 유용

무식하게 푼다 라는 의미 또한 가지고 있어  Brute-Force (브루트 포스) 라고도 불린다.

✅ 입력으로 주어지는 데이터(N)의 크기가 매우 작다. 

✅ 이 문제에서 소수를 구하게 될텐데 소수가 아닌 경우, 최소 하나의 약수가 존재하고 , 그 약수는 항상 n의 제곱근 이하 이므로 Math.sqrt() 메소드 사용 - 제곱근 구하는 메소드

2. DFS(깊이 우선 탐색)

개념: 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

-> 스택 기반 자료구조를 사용한다.

 

대표적은 구현 방법으로는 다음 방법이 있다.

<깊이우선탐색(DFS) 구현 방법>

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

<깊이우선탐색(DFS) 알고리즘 그림 및 과정>

 

1. 0부터 시작해서 스택에 담는다.

2. 0번 노드를 뽑아서 출력 -> 인접노드인 1번 노드를 스택에 담기

3. 1번 노드를 뽑아서 출력 -> 인접노드인 2번, 3번 노드를 스택에 담기

4. 3번 노드를 뽑아서 출력 -> 인접노드인 4, 5번 노드를 스택에 담기
(2번 노드는 이미 스택에 있으므로 제외) ❗여기까지 스택에 2,4,5 순서대로 담겨져 있을 것

5. 5번 노드 뽑아서 출력 -> 인접노드 더 이상 없으므로 스택에 안 담음

6. 스택에 남은 노드인 4, 2를 출력한다.

 

<문제 풀이과정 및 순서도>

 

1.  주어진 문자열 str로부터 가능한 모든 숫자 조합을 생성하여 배열로 반환하는 getPer 함수 구현

✅ ch 배열은 각 문자 사용 여부를 추적하는데 사용. 초기값은 모두 0으로 설정.(1차원 배열)

 

const getPer = (str) => {
    const answer = [];
    const n = str.length;
    let ch = Array.from({ length: n }, () => 0);
    
    const dfs = (curStr) => {
        answer.push(+curStr);
        for (let i = 0; i < n; i++) {
            if (ch[i] === 0) {
                ch[i] = 1;
                dfs(curStr + str[i]);
                ch[i] = 0;
            }
        }
    }
    dfs('');
    answer.shift();
    return answer;
}

 

 

2. 주어진 숫자 n이 소수인지 여부를 판별 하는 isPrime 함수 구현

✅ 반복문 범위를 n의 제곱근까지만 판단하고 약수가 있으면 소수로 판단한다.

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

 

3. getPer함수의 결과물로 반환된 배열의 중복을 제거하고 새로운 배열을 생성한 뒤 배열에서 소수인 숫자들만으로 구성되도록 필터링 한다. 그리고 필터링 한 배열의 길이를 return 해주기

function solution(numbers) {
    return [...new Set(getPer(numbers))].filter(v => isPrime(v)).length;
}

 

<전체 코드>

function solution(numbers) {
    return [...new Set(getPer(numbers))].filter(v => isPrime(v)).length;
}

const getPer = (str) => {
    const answer = [];
    const n = str.length;
    let ch = Array.from({ length: n }, () => 0);
    
    const dfs = (curStr) => {
        answer.push(+curStr);
        for (let i = 0; i < n; i++) {
            if (ch[i] === 0) {
                ch[i] = 1;
                dfs(curStr + str[i]);
                ch[i] = 0;
            }
        }
    }
    dfs('');
    answer.shift();
    return answer;
}

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