프로그래머스 Lv.2 | (완전탐색) 소수찾기 js

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=javascript

 

 

풀이

DFS 방식으로 재귀함수를 이용해 풀음. 다만 반복문에서 같은 수를 선택하지 않기 위해 visited를 두고 관리해 백트래킹함

• 조합을 구하다보면 중복되는 조합이 생길텐데 어떻게 해결하냐 -> 조합한 결과를 Set()에 add한다.
• '11'과 '011' 처럼 앞에 0이 붙을텐데 어떻게 처리할거냐 -> Number('011')을 하면 숫자 11로 변한다.
• 소수 판별은 아예 isPrime()이라는 함수를 만들어 true/false를 반환하게 한다.

1. 모든 가능한 조합을 만들어봐야 한다. 본인을 제외한 문자열을 점층적으로 더하도록 재귀함수를 짠다.
2. 맨 처음 함수에 진입할 때는 빈문자열이므로 그 경우를 제외하고 set에 추가하기 위해 length>0일 때만 수행
3. 이미 사용한 문자열인지는 visited[i]를 이용해 관리한다. 재귀함수에서 빠져나오면서 방문 여부를 해제하도록 재귀함수 호출 다음 줄에 visited[i] = false를 배치해 해지한다.

function solution(numbers) {
    function combination(currNum) {
        if(currNum.length > 0) {
            result.add(Number(currNum));
        }
        for(let i = 0; i < numbers.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                combination(currNum + numbers[i]);
                visited[i] = false;
            }
        }
    }
    
    const result = new Set();
    const visited = new Array(numbers.length).fill(false);
    
    combination('');
    return Array.from(result).filter(isPrime).length;
}

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

 

combination('')를 호출했을 때 벌어지는 일 - numbers가 '1234'인 경우

1. combination('') 호출 시 if문 건너뛰고 for i=0으로 인해 visitied[0]이 방문되었다고 바뀌고, combination('' + '1') 호출
2. result에 1이 추가됨. for 0부터 검사해보니 visited[0] = true라 visited[1]을 true로 바꾸고 combination('12') 호출
3. 반복하다가 combination('1234') 호출하면 result는 [1, 12, 123, 1234]가 됨. visited가 모두 true여서 for문 돌아도 아무 일이 일어나지 않음. stack에서 재귀함수 pop되면서 차례대로 combination() 호출문 뒤에 있던 visited[i] = false로 인해 모두 false로 초기화
4. stack이 모두 pop 되어 최초에 combination('')을 호출했을 때의 for문 중 i=1을 할 차례가 왔음. 그래서 2부터 다시 조합 시작. 이 과정을 거치면 result는 [1, 12, 123, 1234, 2, 21, 213, 2134]가 됨.
5. combination('')의 for문 모두 돌아서 1, 2, 3, 4로 시작하는 모든 조합을 만들게 되었음