문제 출처

코딩테스트 연습 > 완전탐색 > 소수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

종이 조각에 적힌 숫자들이 모인 문자열 numbers가 주어질 때, 이 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하라

접근 방법

문제는 크게 나누면 2가지를 요구한다.

1. 숫자 조합을 만들어라.
2. 소수인지 확인하라.

일단 숫자 조합은 DFS를 이용하여 재귀를 이용하여 풀이한다.
numbers의 길이는 1 이상 7 이하의 문자열이므로,
boolean[] visited = new boolean[7]을 이용하여 문자열의 각 자리 방문 여부 배열을 만든다.
이후 이 방문 여부를 활용하여 조합의 중복 제거가 가능한 set에 이 전에 이미 만들어진 문자열과 방문이 안된 문자열을 가져와 조합하여 추가한다.
이 후 추가 된 숫자의 다음 조합을 알기 위해 dfs를 진행한다.

% "011"의 경우 Set에 들어갈 때 Integer.parseInt를 통해 들어가므로 어차피 11이 되어 들어간다.

소수인지는 확인은 제곱근 최적화 소수 판별을 이용하여 풀이한다.
길이가 2 이하일 땐, 소수가 아니므로 false를 return하고,
해당 숫자의 제곱근만큼 하나씩 다 나머지를 판별했을 때, 통과하게 되면 true를 반환한다.

import java.util.*;

class Solution {
    
    static Set<Integer> set;
    static boolean[] visited = new boolean[7];
    
    public void dfs(String numbers, String s, int depth){
        if(depth > numbers.length()){
            return;
        }
        for (int i = 0; i< numbers.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                set.add(Integer.parseInt(s+numbers.charAt(i)));
                dfs(numbers, s + numbers.charAt(i), depth + 1);
                visited[i] = false;
            }
        }
    }
    
    public boolean isPrime(int n){
        if(n < 2){
            return false;
        }
        
        for(int i = 2; i<= Math.sqrt(n); i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
    
    public int solution(String numbers) {
    int answer = 0;
        set = new HashSet<>();
        dfs(numbers, "", 0);
 
        for (Integer num : set) {
            if (isPrime(num)) {
                answer++;
            }
        }
        
        return answer;
    }
}

Review

import java.util.*;

class Solution {
    
    static boolean visited[] = new boolean[7];
    static Set<Integer> set;
    
    public void permute(String numbers, String str, int depth){
        if(depth > numbers.length()){
            return;
        }
        
        for(int i = 0; i<numbers.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                String s = str + numbers.charAt(i);
                set.add(Integer.parseInt(s));
                permute(numbers,s,depth + 1);
                visited[i] = false;
            }
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        set = new HashSet<>();
        permute(numbers,"",0);
        
        for(int n : set){
            if(n<2){
                continue;
            }else{
                boolean check = true;
                for(int i = 2; i<=Math.sqrt(n); i++){
                    if(n % i == 0){
                        check = false;
                        break;
                    }
                }
                if(check){
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

알게된 점

이 문제는 나에겐 너무 어려웠다. DFS(깊이 우선 탐색)의 이론은 알고 있었지만, 배운지 약 1년 6개월이 되었기도하고, JAVA로는 구현을 해본적이 없어서 조합을 어떻게 진행할지 몰랐다. 하지만 여러 블로그 글을 보니 결국 숫자 조합할 때, 사용한 것은 visited[i] = true, 사용하지 않은 것은 visited[i] = false를 이용해 조합을 만드는 부분에 대해서 알게 되었다.

참고 출처
https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89DFS

% 순열 및 조합을 만드는 코드에 대해서 정리하여 글로 올려야겠다.

문제푼 흔적

Review