[99클럽 코테 스터디 7일차 TIL] DFS를 사용해 소수 찾기 문제 풀이

문제

프로그래머스 - 소수 찾기 문제를 보고 풀이한 내용이다.

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• “013”은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

풀이

class Solution {
    private static HashSet<Integer> set = new HashSet<>();
    
    public int solution(String numbers) {
        int[] nums = new int[numbers.length()];
        for (int i = 0; i < numbers.length(); i++) {
            // 문자열 numbers를 숫자 배열로 만든다
            nums[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        // 방문 내역을 저장할 배열을 생성한다
        boolean[] visited = new boolean[numbers.length()];
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= numbers.length(); i++) {
            // 숫자 배열 nums와 방문 내역 visited를 이용해 모든 경우의 순열을 만든다
            permutation(nums, visited, sb, 0, i);
        }
        
        int answer = 0;
        for (int num : set) {
            // 만들어진 순열들의 소수 여부를 판별해 개수를 센다
            if (isPrime(num)) {
                answer++;
            }
        }
        
        return answer;
    }
    
    private void permutation(int[] nums, boolean[] visited, StringBuilder sb, int depth, int length) {
        if (depth == length) {
            set.add(Integer.parseInt(sb.toString()));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sb.append(nums[i]);
                permutation(nums, visited, sb, depth + 1, length);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }
    
    private boolean isPrime(int n) {
        if (n == 0 || n == 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

HashSet을 사용한 이유

순열을 구하면서 만들어지는 모든 수는 중복을 방지하기 위해 중복을 허용하기 않는 HashSet에 저장했다. 중복을 방지하면서 순열을 생성하면 소수를 판별할 때 중복 계산을 피할 수 있고 연산 효율을 높일 수 있다.

permutation 메서드 - DFS를 사용해 순열 만들기

private void permutation(int[] nums, boolean[] visited, StringBuilder sb, int depth, int length) {
        if (depth == length) {
            set.add(Integer.parseInt(sb.toString()));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sb.append(nums[i]);
                permutation(nums, visited, sb, depth + 1, length);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }

• 재귀적으로 순열을 생성하면서 각 단계마다 방문한 숫자들을 기록하고, 그에 따라 숫자를 조합하여 순열을 만든다.
• 재귀 호출을 통해 모든 가능한 순열을 생성한다.

예를 들어, 주어진 종이 조각이 “011”인 경우를 살펴보자.

         0
        / \
       1   1

위와 같은 트리가 만들어지고, 트리를 순회하며 순열을 만드는 과정은 다음과 같다.

1. 처음에는 0을 선택해 방문한다.
2. 그 다음으로 1을 선택해 방문한다.
3. 그 다음으로 1을 선택해 방문한다.
4. 이제 더 이상 방문하지 않은 노드가 없으므로, 현재까지의 순열을 만들어낸다. 여기서는 "011"이 된다.
5. 이제 이전 단계로 돌아가서 다른 경로를 탐색한다.
6. 두 번째로 1을 선택하여 방문한다.
7. 그 다음으로 0을 선택하여 방문한다.
8. 이제 더 이상 방문하지 않은 노드가 없으므로, 현재까지의 순열을 만들어낸다. 여기서는 "101"이 된다.

이렇게 DFS 탐색을 진행하면 가능한 모든 순열을 생성할 수 있다!

isPrime 메서드 - 소수 판별하기

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

• 주어진 숫자가 소수인지를 판별한다.
• 소수는 1과 자기 자신으로만 나누어지는 수다. 따라서 2부터 해당 수의 제곱근까지의 수로 나누어 보고 하나라도 나누어 떨어지면 소수가 아니다.
• 만약 어떤 수도 나누어 떨어지지 않으면 소수이다.

시간 복잡도

DFS를 사용하여 가능한 모든 순열을 생성하는 데에 O(N!)의 시간이 소요되고, 소수를 판별하는 과정에서 각 숫자에 대해 제곱근까지의 숫자로 나누어보아야 하므로 소수 판별에는 O(√N)의 시간이 필요하다.

즉, 전체적인 시간 복잡도는 O(N! * √N)이 된다.

주어진 제한 조건에서 N은 7까지이기 때문에 사용할 수 있지만, 만약 숫자의 길이가 더 커진다면 지수적으로 시간이 증가한다. 상대적으로 작은 입력에 대해서만 효율적인 알고리즘이다.

done!

99클럽 7일차 출석🎉

99클럽을 신청한지도 벌써 일주일이 되었다.

아직 월요일은 출석이 반영되지 않았는데 어쨌든 일주일동안 빼놓지 않고 하루 한 문제와 TIL 작성을 한 스스로에게 작은 칭찬을 해주고 싶다. 처음엔 Python으로 신청했었는데 Java로 바꾸길 잘한 것 같다. 물론 문법이 익숙치 않아서 공부하는데 시간은 배로 걸리지만.. 그만큼 빠르게 배울 수 있는 것 같다. 재밌다!

앞으로 약 한 달 정도 남았는데, 꼭 끝까지 완주해서 조금이라도 더 성장하고 싶다. 화이팅!