[Java] 프로그래머스 - 소수 찾기

숫자 조각으로 만들 수 있는 모든 수를 완전탐색으로 생성한 뒤, 중복을 제거하고 소수 개수를 구하는 문제

 

1. 문제 유형

완전탐색, 백트래킹(DFS), 구현

 

2. 내가 놓친 포인트

처음 떠올린 접근 : 문자 하나씩 조합해서 숫자를 만들고, set에 넣어서 중복을 제거한 뒤에 그 숫자가 소수인지 검사하면 될 것 같았다.

오답 원인: 풀이 아이디어는 맞았는데 코드로 구현을 못했다.

 

3. 핵심 로직 & 해결 방법

핵심 조건: 주어진 숫자 조각들로 만들 수 있는 모든 길이의 숫자를 만들어야 하며 같은 숫자는 한 번만 세야 한다.

풀이 아이디어:

1. visited[]를 사용해 현재 경로에서 이미 사용한 숫자 조각을 체크한다.
2. dfs를 돌면서 숫자를 한 자리씩 이어 붙여 current를 만든다.
3. current가 비어있지 않다면 Set<Integer>에 넣어 중복을 제거한다
4. dfs가 끝난 뒤 Set에 들어 있는 숫자들을 하나씩 꺼내 소수인지 판별한다.
5. 소수라면 개수를 증가시켜 정답을 구한다.

# 소수 판별 포인트

어떤 수 n이 소수인지 확인할 때는 2 ~ √n까지만 나눠보면 된다.

합성수라면 약수 하나는 반드시 √n 이하에 존재하기 때문이다.

 

4. 구현 코드

import java.util.*;

class Solution {
    Set<Integer> set = new HashSet<Integer>();
    boolean[] visited;
     
    public int solution(String numbers) {
        visited = new boolean[numbers.length()];
        
        dfs(numbers, "");
       
        int answer = 0;
        
        for(int num : set){
            if(isPrame(num)){
                answer++;
            }    
        }
        
        return answer;
    }
    
    public void dfs(String numbers, String current) {
        if (!current.equals("")) {
            set.add(Integer.parseInt(current));
        }
        
        for(int i = 0; i < numbers.length(); i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(numbers, current + numbers.charAt(i));
                visited[i] = false;
            }
        } 
    }
    
    public boolean isPrame(int num) {
        if(num < 2) return false;
        if (num == 2) return true;
        if(num % 2 == 0) return false;
        
        for(int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

시간 복잡도: 대략 O(N! × √M) 

 

• N: 숫자 조각 개수
• M: 만들어지는 숫자의 최대 크기

공간 복잡도: O(N! + N)

• 중복 제거용 Set
• 방문 체크용 visited

 

---

 

인사이트

• visited[i] = true 후 재귀 호출, 종료 후 false로 복구하는 선택 → 재귀 → 복구 패턴이 백트래킹의 기본이라는 걸 다시 학습했다.
• 소수 판별은 무조건 끝까지 나누는 게 아니라 √n까지만 확인하면 충분하다는 점을 문제에 직접 적용해볼 수 있었다.

 

문제 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/42839