[TIL] 99클럽 코테 스터디 23일차 TIL + 프로그래머스 소수찾기

문제 풀이

 

문제 탐색하기

DFS 알고리즘을 활용하여 주어진 값으로 숫자를 만들며 진행하면 됩니다. 숫자를 만들고 그 숫자가 소수인지 판단하는 메소드를 작성하여 소수라면 Set에 저장하게 합니다. Set에 저장하는 이유는 중복되는 숫자가 저장되었을 경우를 대비하기 위함입니다. 

숫자 종이는 숫자를 만들때 한번씩만 사용할 수 있기때문에 DFS 탐색을 반복하면서 방문한 인덱스는 visited 배열에 표시합니다. 그리고 백트래킹을 하기 위해서 재귀호출이 끝나면 visited배열의 값을 초기화 시키도록 합니다. 

 

이렇게 탐색이 끝난 후 set의 size를 출력하면 만들 수 있는 소수의 수를 알아낼 수 있습니다.

 

문제 풀이

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;


class Solution {
    
    static int[] arr;
    static boolean[] visited;
    static Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers){
        arr = new int[numbers.length()];
        for(int i=0; i<numbers.length(); i++) {
            arr[i] = numbers.charAt(i)-'0';
        }

        Arrays.sort(arr);
        visited = new boolean[arr.length];

        dfs(arr, 0, 0);
        return set.size();
    }

    private static void dfs(int[] arr, int number, int loop){
        if(loop == arr.length){
            return;
        }
        
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                int num = number*10 + arr[i];
                if(primality(num)){
                    set.add(num);
                }
                
                visited[i] = true;
                dfs(arr, num, loop+1);
                visited[i] = false;
            }
        }
    }

    private static boolean primality(int n){
        if(n < 2) return false;

        for(int i=2; i<=(int)Math.sqrt(n); i++){
            if(n%i == 0){
                return false;
            }
        }
        return true;
    }
}

 

오늘의 회고

소수를 판단하는 로직이 코테 문제를 풀다보면 가끔 등장하게 되는데 이번 기회에 확실하게 알고 갈 수 있어서 좋습니다. 프로그래머스 피로도 문제를 통해서 백트래킹을 하는 방법을 사용해서 DFS알고리즘으로 문제를 풀 수 있었는데 이 번 문제에서도 배웠던 개념을 사용하여 문제를 풀 수 있어서 좋았습니다!