완전탐색 활용한 알고리즘 문제풀이

오늘 푼 문제: 소수찾기

입출력

• 입력: 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어집니다.
• 출력: 종이 조각으로 만들 수 있는 소수가 몇 개인지 출력

예제 코드

import java.util.*;

class Solution {
    /**
     * 1. 에라토스테네스의 체를 활용하여 조합할 수 있는 최대 숫자까지의 소수여부를 배열에 저장
     * 2. DFS를 활용하여 발생할 수 있는 모든 수의 조합에 대하여 소수인지 확인
     * 3. 중복 카운트를 방지하기 위하여 Set을 활용
     */
    static int N, answer, LENGTH = 10000000;
    static boolean[] isPrime = new boolean[LENGTH + 1]; // 소수 여부를 확인할 배열
    static int[] ch;
    static char[] chars, arr;
    static Set<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        answer = 0;
        N = numbers.length();
        ch = new int[N];
        arr = new char[N];
        chars = numbers.toCharArray();
        findNp();
        for (int i = 1; i <= N; i++) {  
            DFS(0, i);
        }
        return answer;
    }
    
    static void findNp() {
        // 배열의 모든 원소를 true로 할당
        Arrays.fill(isPrime, true);
        // 0과 1은 소수가 아님으로 false로 할당
        isPrime[0] = isPrime[1] = false;
        // n의 모든 약수에 해당하는 약수들은 
        // Math.sqrt(Length) 이하의 숫자이기 때문에 범위를 아래와 같이 정하였다.
        for (int x = 2; x <= Math.sqrt(LENGTH); x++) {
            if (isPrime[x] == true) { // 해당 수가 소수일 경우
                // 해당 소수의 제곱수 ~ LENGTH까지의 모든 숫자 중 해당 소수의 배수에 대하여 false로 할당.
                for (int y = (int) Math.pow(x, 2); y <= LENGTH; y += x) isPrime[y] = false;
            }
        }
    }
    
    static void DFS(int L, int M) {
        if (L == M) {
            // 조합에 대한 문자 배열을 숫자로 치환하는 로직
            String str = "";
            for (int i = 0; i < M; i++) str += arr[i];
            int tmp = Integer.parseInt(str);
            
            // 이미 확인한 수일 경우 건너뛴다.
            if (set.contains(tmp)) return;
            // 소수일 경우 answer을 1 증가시킨다.
            if (isPrime[tmp]) {
                set.add(tmp);
                answer++;
            }
        } else {
            for (int i = 0; i < N; i++) {
                // 만약 사용하지 않은 숫자일 경우 해당 자리(L)에 할당한다.
                if (ch[i] == 0) {
                    ch[i] = 1;
                    arr[L] = chars[i];
                    DFS(L + 1, M);
                    ch[i] = 0;
                }
            }
        }
    }
}

• 주어진 배열에 대하여 n개를 추출하여 만든 조합을 구하는 매서드를 생성했습니다.
• 에라토스테네스의 체를 활용하여 조합할 수 있는 최대값까지의 소수여부를 배열에 저장했습니다.
• 모든 조합에 대하여 소수 여부를 학인해줍니다.

회고

• 에라토스테네스의 체를 이렇게 활용할 줄 몰랐습니다.
• 다시 한번 수학적 사고의 필요성을 느꼈습니다.
• 아직 DFS를 작성할 때 머리속에서 완전히 그려지지 않는 느낌입니다.
• 재귀함수와 그래프를 더 공부해볼 생각입니다.