[프로그래머스] 42839번 : 소수 찾기

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

간단하다. 문자열로 주어지는 numbers 배열에서 주어지는 숫자들로 모든 경우의 수를 탐색해 소수가 되는 숫자가 몇 개인지 반환하는 문제이다.

최대 7자리의 숫자가 주어지는데, 처음엔 그저 dfs 를 통해 탐색하면 되지 않을까 싶었는데 순서또한 고려해줘야 할 문제였다.
즉, 조합이 아니라 순열을 구해야 한다.

import java.util.*;

/*
문자열 최대개수 7 에서 순열을 통해 모든 경우의 수를 파악해서, 소수인지 판별
최대 7! 에 소수판별 알고리즘을 제곱근 시간복잡도로 사용 -> 완전탐색
*/

class Solution {
    
    static int answer = 0;
    static Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        for(int i=1;i<=numbers.length();i++){
            permutation(numbers.split(""), 0, numbers.length(), i);
        }
        return answer;
    }
    
    public void permutation(String[] arr, int depth, int n, int r) {
        if (depth == r) {
            String temp = "";
            for(int i=0; i<r; i++){
                temp += arr[i];
            }
            if (isPrime(Integer.parseInt(temp))) {
                set.add(Integer.parseInt(temp));
                answer++;
            }
        }
        
        for (int i=depth;i<n;i++) { // 순열 알고리즘 기억
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, r);
            swap(arr, depth, i);
        }
    }
    
    public void swap(String[] arr, int depth, int i){
        String temp = arr[i];
        arr[i] = arr[depth];
        arr[depth] = temp;
    }
    
    public boolean isPrime(int num) {
        if (set.contains(num)) return false; // 같은 숫자면 패스
        
        if (num < 2) return false;
        
        for (int i=2; i*i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

블로그를 통해 순열 알고리즘을 알아보았고, swap() 연산이 핵심임을 깨달았다.
백트래킹을 통해 원상태로 복구하는 과정도 잊으면 안된다.

또한 set 자료구조를 통해 이미 연산을 통해 포함된 소수라면 건너뛰었다.