[프로그래머스] 소수 찾기 (Java) — DFS 순열 생성

📌 핵심 요약

• 문제 핵심 — 흩어진 숫자 종이조각으로 만들 수 있는 모든 수 중에서 소수의 개수를 세는 문제
• 핵심 아이디어 — 자리수가 정해져 있지 않으므로 모든 길이의 순열을 DFS로 전부 만들어 본다 (완전탐색)
• 중복 처리 — "011" → 11 처럼 다른 조합이 같은 수가 될 수 있어 Set으로 자동 중복 제거
• 소수 판별 — 2 ~ √n 까지만 나눠봐서 약수가 있으면 소수가 아님

 

목차

1 문제 소개

숫자가 적힌 종이 조각이 흩어져 있습니다. 이 조각들을 붙여서 만들 수 있는 수 중에서 소수가 몇 개인지 세는 문제입니다. 예를 들어 "17" 이라면 1, 7, 17, 71 을 만들 수 있고, 이 중 소수는 7, 17, 71 세 개입니다.

Programmers Lv.2

소수 찾기

numbers 길이 1 ~ 7 · 각 자리 0~9

분류: 완전탐색

한 자리 숫자가 적힌 종이 조각이 흩어져 있습니다. 흩어진 종이 조각을 붙여 만들 수 있는 소수가 몇 개인지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 만들 수 있는 소수의 개수를 반환하세요.

제약 조건

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"처럼 0으로 시작하는 수도 만들 수 있으며, 이 경우 13으로 취급합니다.

2 접근 방법

왜 완전탐색(DFS)인가?

숫자의 개수가 최대 7개로 매우 적습니다. 그리고 "몇 자리 수를 만들지"가 정해져 있지 않기 때문에, 1자리부터 전체 자리까지 모든 순열을 만들어 봐야 합니다.

이렇게 경우의 수가 작고 가능한 모든 조합을 직접 만들어 확인하는 상황이 바로 완전탐색(브루트포스)이고, 순열을 만드는 데에는 DFS(재귀)가 가장 자연스럽습니다.

ℹ️

순열의 개수는 충분히 작다

숫자 7개일 때 만들 수 있는 모든 길이의 순열 수는 약 7 + 7·6 + … + 7! ≈ 13,700개 정도입니다. 각 수에 소수 판별을 해도 시간 안에 충분히 통과합니다.

핵심 아이디어 3가지

1. DFS로 순열 생성 — 남은 숫자에서 한 글자씩 골라 현재 조합 뒤에 붙이고, 고른 글자는 빼고 재귀 호출합니다.
2. Set으로 중복 제거 — "011"과 "11"은 둘 다 11이 되므로, HashSet<Integer>에 넣어 중복을 자동으로 거릅니다.
3. 소수 판별 (√n 까지만) — 2부터 √n까지만 나눠 보면 됩니다. 약수는 항상 √n을 기준으로 짝을 이루기 때문입니다.

3 풀이 코드

전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    // 만들어진 수를 중복 없이 저장 (011 과 11 은 같은 11 로 취급)
    Set<Integer> set = new HashSet<>();

    public int solution(String numbers) {
        int answer = 0;

        // 1. 만들 수 있는 모든 숫자 조합을 DFS로 생성
        dfs(numbers, "");

        // 2. 생성된 수 중 소수만 카운트
        for (int num : set) {
            if (isPrime(num)) {
                answer++;
            }
        }

        return answer;
    }

    // DFS: 남은 숫자(numbers)에서 한 글자씩 골라 조합(comb)을 완성
    public void dfs(String numbers, String comb) {
        // 3. 빈 문자열이 아니면 숫자로 변환해 Set에 저장
        if (!comb.equals("")) {
            set.add(Integer.parseInt(comb));
        }

        // 4. 남은 숫자 중 하나(i번째)를 골라 comb에 붙이고,
        //    그 글자는 빼고(substring으로 제거) 재귀 호출
        for (int i = 0; i < numbers.length(); i++) {
            dfs(numbers.substring(0, i) + numbers.substring(i + 1),
                comb + numbers.charAt(i));
        }
    }

    // 소수 판별: 2 ~ √n 까지 나눠떨어지는 수가 있으면 소수가 아님
    public boolean isPrime(int n) {
        if (n <= 1) return false;   // 0, 1 은 소수가 아님
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

DFS 동작 단계별 설명

예시

numbers = "17" 일 때 DFS 흐름

1. dfs("17", "") — comb이 비어 있으므로 저장하지 않고, "1"과 "7"을 각각 골라 재귀
2. dfs("7", "1") — 1 저장 → 남은 "7"을 붙여 dfs("", "17")
3. dfs("", "17") — 17 저장 → 남은 숫자가 없어 재귀 종료
4. dfs("1", "7") — 7 저장 → 남은 "1"을 붙여 dfs("", "71")
5. dfs("", "71") — 71 저장 → 종료. Set = {1, 17, 7, 71}
6. 이 중 소수는 7, 17, 71 → 정답 3

4 핵심 포인트 정리

💡

Set이 중복뿐 아니라 "앞자리 0" 문제까지 해결

Integer.parseInt("011") 은 11 을 반환합니다. 따라서 앞에 0이 붙은 조합을 따로 처리하지 않아도, 정수로 변환하는 순간 자연스럽게 같은 수로 합쳐지고 Set이 중복을 걸러줍니다.

💡

소수 판별은 왜 √n 까지만?

n = a × b 라면 a와 b 중 하나는 반드시 √n 이하입니다. 그러니 √n까지 검사해서 약수가 없으면 그 위쪽도 없는 것이 확정됩니다. 검사 범위를 n에서 √n으로 줄이는 핵심 최적화입니다.

⚠️

Math.sqrt(n)를 반복문 조건에 직접 쓰면?

i <= Math.sqrt(n) 은 반복마다 sqrt를 다시 계산합니다. 이 문제는 입력이 작아 통과하지만, 더 큰 입력에서는 for (int i = 2; (long) i * i <= n; i++) 처럼 제곱으로 비교하면 실수 연산 없이 더 빠르고 안전합니다.

시간 복잡도

단계	내용	복잡도
순열 생성	모든 길이의 순열 (최대 7개 숫자)	≈ 13,700개
소수 판별	각 수마다 2 ~ √n 검사	O(√n)
전체	입력 크기가 작아 충분히 통과	통과

ℹ️

마무리

"경우의 수가 작다 + 모든 자리수 조합을 다 만들어야 한다" 라는 신호를 보고 DFS 완전탐색을 떠올리는 것이 이 문제의 핵심입니다. 중복은 Set으로, 소수 판별은 √n 최적화로 깔끔하게 마무리할 수 있습니다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.