[프로그래머스] 소수 찾기 (DFS)

문제 소개

오늘 풀었던 소수 찾기 - 프로그래머스 문제를 정리합니다.
이 문제는 주어진 숫자 조각들을 조합해 만들 수 있는 수 중 소수가 몇 개인지 찾는 완전탐색 문제입니다.
핵심은 모든 순열을 생성해 중복 없이 정수로 만들고, 각 정수에 대해 소수 판별을 수행하는 데 있습니다.

문제 링크: 소수 찾기 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 가능한 모든 숫자 조합을 만들어야 하므로 문자열 순열 생성
2. 생성된 조합은 문자열이므로 정수로 변환 후 Set에 저장 (중복 제거)
3. Set에 저장된 모든 정수에 대해 소수 여부 판별
4. 소수인 경우 개수 카운팅

---

해결 과정 및 코드

핵심 아이디어

1. 주어진 문자열에서 가능한 모든 조합을 만들기 위해 DFS 방식으로 순열을 생성
   → prefix에 하나씩 붙여가며 remaining을 줄이는 방식
2. 조합된 문자열을 정수로 바꾸고 Set에 저장해 중복 제거
3. 저장된 모든 숫자에 대해 isPrime 함수를 통해 소수 판별
   → 2 이상부터 시작하며 √n까지만 나눠보는 방식으로 최적화

코드

시간 복잡도 : O(n! × √m)
이유: n자리 수의 순열은 최대 n!개, 각 숫자에 대해 √m만큼 소수 판별이 필요

 

import java.util.*;

public class Solution {

    // 소수 판별 함수
    public static boolean isPrime(int num) {
        if (num < 2) return false;  // 2보다 작은 수는 소수가 아님
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;  // 나누어 떨어지면 소수 아님
        }
        return true;
    }

    // DFS를 이용해 모든 조합을 생성하고 Set에 저장
    public static void dfs(String prefix, String remaining, Set<Integer> numberSet) {
        if (!prefix.equals("")) {
            numberSet.add(Integer.parseInt(prefix));  // 숫자로 변환해 저장
        }

        for (int i = 0; i < remaining.length(); i++) {
            // 현재 문자를 prefix에 추가하고, 그 문자를 제외한 나머지로 재귀 호출
            dfs(prefix + remaining.charAt(i),
                remaining.substring(0, i) + remaining.substring(i + 1),
                numberSet);
        }
    }

    public static int solution(String numbers) {
        Set<Integer> numberSet = new HashSet<>();  // 중복 제거를 위한 Set
        dfs("", numbers, numberSet);               // 모든 순열 생성

        int count = 0;
        for (int num : numberSet) {
            if (isPrime(num)) count++;  // 소수인 경우 개수 증가
        }
        return count;
    }
}