[완전탐색] 소수 찾기 - JAVA

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

코딩테스트 연습 - 소수 찾기

---

이 문제는 이름은 소수 찾기이지만 사실 소수 판별 알고리즘은 그리 어렵지 않다

2부터 자기 자신까지 반복문으로 나눠가며 나눠지는지 확인하면 되는데 이는 비효율적이다

그래서 사용한 것은 에라토스테네스의 접근이다

에라토스테네스의 접근이란 2부터 루트 n까지만 검사하면 된다는거다

 

그래서 이건 쉬웠는데..

입력받은 문자열로 모든 순열의 조합들을 뽑아내는 과정이 어려웠다..

그래서 순열 알고리즘?으로 시도했지만 장렬히 실패,,,

사실 아직도 왜 실패했는지는 모른다

그냥 백트래킹으로 풀었다

 

---

※ 백트래킹이란?

재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인중인 상태가 제한 조건에 위배되는지 판단하고, 위배되는 경우 해당 상태를 제외하고 다음 단계로 나아가는 방식이다

 

즉, 재귀를 사용하되 유망하지 않은 상태의 경우는 제외하고 다음 상태로 넘어가는 것이다

(이렇게 유먕하지 않은 상태를 제외하는 것을 가지치기(pruning)이라고 한다)

 

백트래킹을 사용하는 알고리즘에는 대표적으로 DFS가 있다

DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 후 다시 돌아와서 가장 최적의 경로를 반환한다

 

백트래킹으로 해결할 수 있는 문제는 의사 결정, 최적화, 열거하기 등이 있다

---

아무튼 아래는 코드!

 

자바 코드)

import java.util.*;

class Solution {
    static boolean[] visited;
    static Set<Integer> map = new HashSet<>();
    
    public int solution(String numbers) {
        visited = new boolean[numbers.length()];
        backTracking(0, numbers, "");
        return map.size();
    }
    
    public static void backTracking(int depth, String numbers, String current) {
        if (depth == numbers.length()) {
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                String number = current + numbers.charAt(i);

                if (isPrime(Integer.parseInt(number))) {
                    map.add(Integer.parseInt(number));
                }

                backTracking(depth + 1, numbers, number);
                visited[i] = false;
            }
        }
    }

    public static boolean isPrime(int n) {
        if(n==0 || n==1) {
            return false;
        }

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

백트래킹을 사용해서 애초에 소수가 아닌 애는 map에 추가하지 않는다

그리고 map은 중복 제거를 위해 HashSet을 사용하였다

 

 

음... 끝!