소수 찾기

2026.05.18

문제 설명

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

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

제한사항

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

입출력 예

문제 풀이

1차 실행 오류

---

소수 판별에 오류 발생
n == 4일 때 소수로 판정됨

---

import java.util.Set;
import java.util.HashSet;

class Solution {
    private Set<Integer> set = new HashSet<>(); // 소수를 저장할 해시
    private boolean[] visited;
    private int len;
    
    public boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i < n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    public void dfs(String numbers, StringBuilder sb) {
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sb.append(numbers.charAt(i));
                int n = Integer.parseInt(sb.toString());
                if (isPrime(n)) { // 소수일 때
                    set.add(n);
                }
                dfs(numbers, sb);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }
    
    public int solution(String numbers) {
        StringBuilder sb = new StringBuilder();
        len = numbers.length();
        
        visited = new boolean[len];
        for (int i = 0; i < len; i++) {
            visited[i] = false;
        }
        
        dfs(numbers, sb);
        
        return set.size();
    }
}

나의 코드

소요 시간: 43분

시간 복잡도: O($n!$)

---

코드 채점 전 실행을 하면서 StringBuilder의 값을 원래대로 돌리지 않고
계속 루프를 돌아서 값이 계속 누적되는 오류가 발생했음

자주 풀던 정수 탐색의 경우 dfs(count + 1)와 같은 형태로
기존 객체의 값이 변경되지 않아 문제가 없었지만,

이와 같이 객체 값을 변경하는 경우엔 원래대로 되돌리는 과정이 필요함

boolean의 기본 초기화는 false

---

import java.util.Set;
import java.util.HashSet;

class Solution {
    private Set<Integer> set = new HashSet<>(); // 소수를 저장할 해시
    private boolean[] visited;
    private int len;
    
    public boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    public void dfs(String numbers, StringBuilder sb) {
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sb.append(numbers.charAt(i));
                int n = Integer.parseInt(sb.toString());
                if (isPrime(n)) { // 소수일 때
                    set.add(n);
                }
                dfs(numbers, sb);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }
    
    public int solution(String numbers) {
        StringBuilder sb = new StringBuilder();
        len = numbers.length();
        
        visited = new boolean[len];
        for (int i = 0; i < len; i++) {
            visited[i] = false;
        }
        
        dfs(numbers, sb);
        
        return set.size();
    }
}

AI 코드

시간 복잡도: O($n!$)

import java.util.Set;
import java.util.HashSet;

class Solution {
    private Set<Integer> set = new HashSet<>();
    private boolean[] visited;
    private int len;

    public boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public void dfs(String numbers, StringBuilder sb) {
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sb.append(numbers.charAt(i));
                int n = Integer.parseInt(sb.toString());
                if (isPrime(n)) set.add(n);
                dfs(numbers, sb);
                sb.deleteCharAt(sb.length() - 1);
                visited[i] = false;
            }
        }
    }

    public int solution(String numbers) {
        len = numbers.length();
        visited = new boolean[len];
        dfs(numbers, new StringBuilder());
        return set.size();
    }
}