[프로그래머스][JAVA] 소수 찾기 - dfs

📌 문제

프로그래머스  | 소수찾기 | level2 | 완전탐색

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

프로그래머스

 

 

📌 문제 탐색하기

• 출력 : 소수를 몇개 만들 수 있는지 알아내기
• 각 종이에 적힌 숫자 배열 numbers에 따라, 소수 몇개 만드는지 확인하기

ex) 17 = 7, 17, 71

 

📌 알고리즘

• numbers를 먼저 각 숫자로 배열로 분리한 후에
• 완전탐색(dfs)를 통해 깊이우선탐색으로 숫자를 활용한 경우들의 모두 찾고
  • numbers가 1~7까지의 길이이기에 아무리 많은 완전탐색이더라도, 7!이므로 충분히 가능하다.
• 이 부분이 소수인지를 확인해야함

⇒ dfs + 소수 메소드

 

 

📌 코드 설계하기

1. numbers 분해
2. dfs
3. 소수 메소드 작성

 

 

📌 소수찾기 메소드 

소수

소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다.

이를 찾기 위해선 사실상 2 ~ 자기자신 - 1 까지 FOR문으로 돌며 나눠지는게 있는지 확이하면 되는데 불필요한 계산이 많이 필요하다.

이러한 계산을 줄이기 위한 개선점으로는 2 ~ '제곱근' 까지만 찾으면 된다. 

 

ex) 16

1 * 16

2 * 8

4 * 4

8 * 2

16 * 1

 

→ 가운데 약수인 4를 기준으로 각 등식이 대칭적인 형태이므로, '가운데' 약수까지만 '나누어떨어지는지' 확인하면 된다. 

→ 그 '가운데' 약수는 곧 제곱근으로 표현될 수 있다. 

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

 

 

📌 정답 코드 비교

## 최근 풀이 ##
import java.util.*;
import java.io.*;

class Solution {
    static String[] number;
    static int[] visited;
    static HashSet<Integer> numSet = new HashSet<>(); //중복없이 구현
    public int solution(String numbers) {
        int answer = 0;
        number = numbers.split("");
        visited = new int[number.length];
        dfs("");
        
        for(int num : numSet){
            if(isPrime(num)){
                answer++;
            }
        }
        
        return answer;
    }
    
    public void dfs(String combineNum){
        if(!combineNum.equals("") && combineNum.charAt(0) != '0'){ 
        //숫자여야하므로 0 이 앞에 올 수 없
            numSet.add(Integer.parseInt(combineNum));
        }
        for(int i = 0; i<number.length; i++){
            if(visited[i] == 0){ //가지치기 pruning
                combineNum += number[i];
                visited[i] = 1;
                dfs(combineNum);
                visited[i] = 0;
                combineNum = combineNum.substring(0, combineNum.length()-1);
            }
        }
    }
    
    public boolean isPrime(int num){
        if(num < 2){
            return false;
        }
        for(int i = 2; i<=Math.sqrt(num); i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
}

## 과거 풀이 ##
import java.util.*;
import java.io.*;

// 소수 판단 함수 + dfs 방식으로 찾는 함수를 구현 
// dfs 함수를 구현할 때, String값을 Integer로 변경하여 찾을 수 잇는 값 전부를 중복없이 리스트에 담기
// 리스트에 담긴 값들을 소수판단하여 세준다

class Solution {
    static ArrayList<Integer> arr = new ArrayList<>();
    static boolean[] check = new boolean[7]; //최대 7자리수
    

    public int solution(String numbers) {
        int answer = 0;
        
        for(int i = 0; i<numbers.length(); i++) {
            dfs(numbers, "", i+1);
        }
        
        for(int i = 0; i<arr.size(); i++){
            if(isPrime(arr.get(i))){
                answer++;
            }
        }
        
        return answer;
        
        
    }
    
    //dfs를 활용한 백트래킹 방법
    public void dfs(String str, String tmp, int m) {
        
        if(tmp.length() == m){
            int num = Integer.parseInt(tmp);
            if(!arr.contains(num)){
                arr.add(num);
            }
        }
        
        
        for(int i = 0; i<str.length(); i++){
            if(!check[i]){
                check[i] = true;
                tmp += str.charAt(i);
                dfs(str,tmp, m);
                check[i] = false;
                tmp = tmp.substring(0, tmp.length()-1);
            }
        }
        
    }
    
    public boolean isPrime(int num) {
        
        if(num < 2){
            return false;
        }
        
        for(int i = 2; i<= Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

과거에도 해당 문제를 풀었는데, 그때는 numbers를 애초에 돌면서 dfs를 시작했지만, 이번에는 먼저 split 배열을 만들어 두고, 이를 통해 완탐을 활용한 전체 숫자를 소수로 판별하는 로직으로 구현했다.

문제를 풀면서 풀이 과정이 간결해지고, 구체화 되어가는 과정에 있다는 것을 깨달을 수 있었다. 👟👟