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

문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

1. 내 풀이

에라토스테네스의 체를 이용했다. 문제 풀 당시 가장 효율적인 풀이는 기억이 안나서 원리만 간단히 차용해서 풀이했다.

1) 에라토스테네스의 체를 만든다.
2) dfs를 돌며 숫자를 만들고, 에라토스테네스의 체를 이용해 해당 수가 소수인지 확인한다음, 소수이면 Set에 넣는다.
set은 순서 보장이 안되고 중복이 불가한 특징이 있다. 해당 문제에서는 set 안의 개수만 세면 되었기 때문에 그냥 사용했다.

import java.util.*;

class Solution {
    String str;
    static int[] eratostenes;
    static Set<Integer> set;
    static boolean[] visited;
    public int solution(String numbers) {
        visited = new boolean[numbers.length()];
        // 에라토스테네스의 체: 1 - 소수, -1 - 소수가 아님, 0 - 검사안함
        eratostenes = new int[9999999];
        for(int i = 2; i <9999999; i++){
            if(eratostenes[i] == 0) {
                eratostenes[i] = 1;
                for(int j = i*2; j < 9999999; j += i) {
                    eratostenes[j] = -1;
                }
            }
        }

        str = numbers;

        // 완전탐색
        set = new HashSet<>();
        dfs("");

        return set.size();
    }

    void dfs(String number) {
        if(number.length() >= 8) return;
        if(!number.equals("") && eratostenes[Integer.parseInt(number)] == 1) {
            set.add(Integer.parseInt(number));
        }

        for(int i = 0; i < str.length(); i++){
            // 중복 x
            if(visited[i]) continue;
            visited[i] = true;
            dfs(number + str.charAt(i));
            visited[i] = false;
        }
    }
}

2. 더 효율적인 에라토스테네스의 체

• int -> boolean
• j = i * i인 이유 : 이미 그 전에 걸러졌기 때문
  • 5의 배수는 10, 15, 20이지만 i = 2, 3일 때 이미 10,15,20은 지워진 상태
• i * i < 10000000인 이유 : 어차피 i보다 작은 수들의 배수로 다 지워지기 때문에
  • N이 100인 경우, i = 11부터는 j가 121이 되어서 이미 범위 100을 넘어버린다. 코드와 함께 이해하면 이해하기 쉬울 것

import java.util.*;

class Solution {
    String str;
    static boolean[] eratostenes, visited;
    static Set<Integer> set;
    public int solution(String numbers) {
        visited = new boolean[numbers.length()];
        // 에라토스테네스의 체: false - 소수, true - 소수가 아님
        eratostenes = new boolean[10000000];
        eratostenes[0] = eratostenes[1] = true;
        for(int i = 2; i*i <10000000; i++){
            for(int j= i*i; j<10000000; j+=i)
              eratostenes[j] = true;
        }

        str = numbers;
        set = new HashSet<>();
        dfs("");

        return set.size();
    }

    void dfs(String number) {
        if(number.length() >= 8) return;
        if(!number.equals("") && !eratostenes[Integer.parseInt(number)]) {
            set.add(Integer.parseInt(number));
        }

        for(int i = 0; i < str.length(); i++){
            // 중복 x
            if(visited[i]) continue;
            visited[i] = true;
            dfs(number + str.charAt(i));
            visited[i] = false;
        }
    }
}

 

기존 코드 시간	더 효율적인 코드 시간
약 300ms	약 200ms