프로그래머스 소수 찾기 자바 풀이

문제 풀이 시간 :

문제 요약

한 자리 숫자가 적힌 종이 조각들을 이어 붙여 만들 수 있는 수 중 소수의 개수를 구하는 문제
문자열 numbers의 길이는 1 이상 7 이하
종이 조각을 일부만 사용해도 되고, 순서를 바꿔서 붙여도 됨
"011"과 11처럼 앞에 0이 붙어 같은 값이 되는 경우는 하나로 취급

문제 풀이

처음엔 만들 수 있는 모든 숫자 조합을 문자열로 만든 다음, 각 숫자마다 소수 판별 함수를 그때그때 호출하면 되겠다고 생각했다.

하지만 numbers의 길이가 최대 7이면 만들 수 있는 조합의 수가 최대 7 + 7*6 + 7*6*5 + ... 로 13,699개에 달하고, 만들어지는 수도 최대 7자리(9,999,999에 가까운 값)까지 나올 수 있다.

조합마다 매번 O(√n) 소수 판정을 새로 돌리면 호출이 겹칠 때마다 같은 계산을 반복하게 된다.

이 문제의 핵심은 에라토스테네스의 체로 10,000,000 이하 소수를 미리 다 걸러두면, 이후에는 배열 조회만으로 소수 판정을 끝낼 수 있다는 점이다.

isPrime 배열을 0부터 9,999,999까지 만들어 두고 체를 한 번만 돌린다.
DFS로 숫자 조각을 하나씩 골라 만들 수 있는 모든 수를 만들고, visited 배열로 같은 조각을 중복 사용하지 않게 막는다.
만들어진 수가 소수면 Set<Integer>에 넣어서, 011과 11처럼 같은 값이 되는 경우를 자동으로 중복 제거한다.

최종 코드

java

import java.util.*;

class Solution {
    public boolean[] isPrime;
    public String[] number;
    
    public void prime(){
        for(int i=0;i<10000000;i++){
            isPrime[i] = true;
        }
        
        isPrime[0] = false;
        isPrime[1] = false;
        
        for(int i=2;i<Math.sqrt(10000000);i++){
            if(isPrime[i]){
                for(int j=i*i;j<10000000;j+=i){
                    isPrime[j] = false;
                }
            }
        }
    }
    
    public Set<Integer> ans;
    
    public boolean[] visited;
    
    public void dfs(String current){
        if(!current.isEmpty()){
            int num = Integer.parseInt(current);
            if(isPrime[num]){
                ans.add(num);
            }
        }
        
        for(int i=0;i<number.length;i++){
            if(!visited[i]){
                visited[i] = true;
                dfs(current+number[i]);
                visited[i] = false;
            }
        }
    }
    
    public int solution(String numbers) {
        
        isPrime = new boolean[10000000];
        prime();
        number = new String[numbers.length()];
        for(int i=0;i<numbers.length();i++){
            number[i] = numbers.substring(i,i+1);
        }
        
        ans = new HashSet<>();
        visited = new boolean[numbers.length()];
        
        dfs("");
        
        return ans.size();
    }
}

소수 찾기

문제 풀이 시간 :

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기