[Algorithms] 프로그래머스 Level 2 소수 찾기

💡Remark
DFS 재귀 호출 시 변동이 있는 매개 변수를 넣을 때 주의해야 한다. 그 이유는 재귀 호출을 할 때에는 매번 하나의 root 에서 살을 붙이는 방식을 사용하는데, root 자체에 변화를 주면 안되고 root 에 살을 하나 붙인 값에 대해 재귀 호출하고, 다시 root 그대로에 다른 살 하나를 붙인 값을 재귀 호출하는 식으로 root 에 변화가 생겨서는 안되고 매개 변수에만 변화되는 모양을 추적할 수 있게 넣어주어야 하기 때문이다.

문제

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

프로그래머스

코드

소수 찾기 문제는 DFS 로 모든 만들 수 있는 숫자를 생성한 뒤, 소수인 것만 개수를 세어서 반환해주면 되는 문제이다. 아래와 같은 코드를 작성했다.

import java.util.*;
// 종이 조각이 흩어져 있음
// 소수를 몇 개를 만들수 있을까?
// 문자열 numbers 가 주어졌을 때,
// 만들 수 있는 소수의 개수를 구하여라
// 우선 숫자들을 모두 만들고, 그 중 소수를 찾는다.
// 숫자의 조합은 여러개인데, 여러 조합 중 소수인 것을 찾을 방법은 여러개이다.
// 여러 숫자의 조합 모두 찾을 수 있다.
class Solution {
    boolean[] visited;
    char[] loopThru;
    List<Integer> allNums = new ArrayList<>();
    
    public void generate(char start, String current) {
        if (start != ' ' && !allNums.contains(Integer.parseInt(current)))
            allNums.add(Integer.parseInt(current));
        if (current.length() == loopThru.length) {
            return;
        }
        
        for (int i = 0; i < loopThru.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            generate(loopThru[i], current + loopThru[i]);
            visited[i] = false;
        }
    }
    
    public boolean isPrime(int num) {
        if (num == 0 || num == 1) return false;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public int check(List<Integer> nums) {
        int cnt = 0;
        for (int n : nums) {
            if (isPrime(n)) cnt++;
        }
        return cnt;
    }
    
    public int solution(String numbers) {
        int answer = 0;
        loopThru = numbers.toCharArray();
        visited = new boolean[numbers.length()];
        generate(' ', "");
        System.out.println(allNums);
        answer = check(allNums);
        return answer;
    }
}