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

문제

주어진 numbers들을 재조합해 소수의 갯수를 찾는 문제이다.

 

---

풀이방법

풀이 시간 : 20분

풀이 방법 : 완전탐색

 

크게보면 2가지로 나눌 수 있다.

 

1. 주어진 numbers들을 이용해 새로운 조합 만들기
2. 만들어진 조합수들이 소수인지 확인하기

1. 조합 만들기

 - 백트래킹에서는 현재까지 만든 숫자 문자열(current)과 방문 여부 배열(visited)을 이용해 1자리부터 n자리까지 모든 숫자 조합을 생성했다. 이 과정에서 같은 숫자가 여러 번 조합될 수 있으므로, 중복을 방지하기 위해 Set을 사용해 생성된 숫자를 저장했다.

 

2. 소수 찾기

- 이제 이렇게 만들어진 숫자들이 소수인지 확인해줘야 하는데, 여기서 중요한건 소수 판별의 효율성이다. 단순하게 2부터 number - 1 까지 나누는 방식은 너무 비효율적이다. 대신, √number까지만 나눠보면 충분하다. 왜냐하면 어떤 수가 소수가 아니라면, 반드시 √number 이하의 약수를 하나 이상 가지고 있기 때문이다.

 

그래서 for (int i = 2; i * i <= number; i++)처럼 구현하면 불필요한 연산을 줄여 성능이 훨씬 좋아진다.

---

코드 

import java.util.*;
import java.io.*;

class Solution {
    static Set<Integer> list;
    static char[] arr;
    static boolean[] visited;
    public int solution(String numbers) {
        int answer = 0;
        list = new HashSet<>();
        int len = numbers.length();
        
        arr = new char[len];
        visited = new boolean[len];
        
        for(int i = 0; i < len; i++){
            arr[i] = numbers.charAt(i);
        }
        
        generateCombinations("");
        
        return list.size();
    }
    
    private static void generateCombinations(String current) {
        if (!current.isEmpty()) {
            int num = Integer.parseInt(current);
            if (checkPrimes(num)) {
                list.add(num);
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                generateCombinations(current + arr[i]);
                visited[i] = false;
            }
        }
    }

    
    private static boolean checkPrimes(int number){
        if(number < 2) return false;

        for(int i = 2; i * i <= number; i++){
            if(number % i == 0){
                return false;
            }
        }
        return true;
    }
}