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

프로그래머스

---

• 문제

문자열은 0-9의 숫자로 이루어져있고, 길이는 최대 7을 가진다.

 

해당 문자열의 숫자 조합으로 이루어진 소수의 개수를 구해야 한다.

 

 

• 풀이

생각해낸 풀이는 아래와 같다.

1. 미리 boolean 배열을 통해 소수인지 아닌지 판별해놓는다. (최대 1000001 크기가 된다.)

2. backtracking을 통해 숫자를 하나씩 골라가며 String을 만들어준다. (visited를 체크하여 같은 index의 수가 중복 추가되지 않게 한다.)

3. 만들어진 수가 소수인지 판별하여 소수가 아니라면 HashSet에 추가한다. (HashSet을 사용하는 이유는 contains를 사용할 때 O(1)의 시간복잡도를 가지기 때문이다.)

코드 답안이 통과되고 다른 사람의 코드를 보며 깨달은 부분이 있다.

아래 부분에 추가했으니 궁금한 사람들은 보면 좋을 것 같다.

 

 

• 코드

import java.util.*; 

class Solution {
    static boolean[] primes;
    static boolean[] visited;
    static Set<Integer> set;
    
    public static int solution(String numbers) {
        set = new HashSet<>();
        primes = new boolean[10000001];
        primes[0] = true;
        primes[1] = true;
        for(int i = 2; i < 10000001; i++) {
            for(int j = i+i; j < 10000001; j+=i) {
                if(primes[j]) continue;

                primes[j] = true;
            }
        }

        visited = new boolean[numbers.length()];
        backtracking(numbers, 0, "");

        return set.size();
    }

    public static void backtracking(String number, int depth, String s) {
        if(depth == number.length()) {
            if(s.equals("")) return;
            int realNumber = Integer.parseInt(s);
            if(primes[realNumber]) return;
            if(set.contains(realNumber)) return;

            //System.out.println(realNumber);
            set.add(realNumber);
            return;
        }

        backtracking(number, depth+1, s);
        for(int i = 0; i < number.length(); i++) {
            if(visited[i]) continue;

            visited[i] = true;
            backtracking(number, depth+1, s+number.charAt(i));
            visited[i] = false;
        }
    }
}

정확성에서 100이 나오긴 했지만, 시간이 너무 오래 걸리는 듯한 느낌이다.

 

다른 사람풀이를 구경해보자.

import java.util.HashSet;
class Solution {
    public int solution(String numbers) {
        HashSet<Integer> set = new HashSet<>();
        permutation("", numbers, set);
        int count = 0;
        while(set.iterator().hasNext()){
            int a = set.iterator().next();
            set.remove(a);
            if(a==2) count++;
            if(a%2!=0 && isPrime(a)){
                count++;
            }
        }        
        return count;
    }

    public boolean isPrime(int n){
        if(n==0 || n==1) return false;
        for(int i=3; i<=(int)Math.sqrt(n); i+=2){
            if(n%i==0) return false;
        }
        return true;
    }

        public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        //if (n == 0) System.out.println(prefix);
        if(!prefix.equals("")) set.add(Integer.valueOf(prefix));
        for (int i = 0; i < n; i++)
          permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), set);

    }

}

가장 많은 칭찬이 달린 풀이이다. 복사해서 붙여넣기 한다음 채점해보자.

나의 풀이보다 약 1/100의 시간이 걸리는 모습이다. 어디서 이런 차이가 발생할까??

 

소수를 구하는 약 O(n^2)의 2중 반복문이 많은 시간을 잡아먹는다.

import java.util.*; 

class Solution {
    
    public static int solution(String numbers) {
        boolean[] primes = new boolean[10000001];
        for(int i = 2; i < 10000001; i++) {
            for(int j = i+i; j < 10000001; j+=i) {
                if(primes[j]) continue;

                primes[j] = true;
            }
        }

        return 3;
    }

}

이를 테스트 해보기위해 위의 코드로 한번 돌려보았다. 

해당 코드에서 일단 많은 시간을 잡아먹는 모습이다. 생각보다 숫자의 종류가 많지 않기때문에 미리 소수인지 아닌지 구해놓기 보다는 하나의 숫자마다 소수인지 아닌지 판별하는 방식이 더 효율적이다.