[프로그래머스] 완전탐색 - 소수 찾기 (Java)

프로그래머스 코딩테스트 연습 - 완전탐색/소수 찾기 (https://programmers.co.kr/learn/courses/30/lessons/42839)

코딩테스트 연습 - 소수 찾기 | 프로그래머스

완전탐색 중에서도 순열(Permutation) 알고리즘을 이용한 문제라고 할 수 있습니다. 순열 알고리즘에 대한 내용은 이해하기 가장 편했던 어떤 블로거분의 설명을 아래에 링크 걸어두겠습니다. 

 

HashSet은 중복을 허용하지 않기 때문에 순열 알고리즘 과정에서 중복 숫자를 자동적으로 처리할 수 있습니다.

 

import java.util.HashSet;
import java.util.Set;
 
public class Solution {
    public int solution(String numbers) {
        int[] numbList = new int[numbers.length()];
        for (int i = 0; i < numbers.length(); i++) {
            numbList[i] = Integer.parseInt(String.valueOf(numbers.charAt(i)));
        }
        
        for(int i = 0; i < numbList.length; i++){
            for(int j = 0; j < numbList.length - i - 1; j++){
                if(numbList[j] > numbList[j+1]){
                    int temp = numbList[j];
                    numbList[j] = numbList[j+1];
                    numbList[j+1] = temp;
                }
            }
        }
 
        Set<Integer> primeList = new HashSet<>();
        for (int i = 1; i <= numbList.length; i++) {
            perm(numbList, 0, i, primeList);
        }
 
        return primeList.size();
    }
      public void perm(int[] arr, int depth, int k, Set primeList) {
        if (depth == k) { 
            returnNumber(arr, k, primeList);
            return;
        } else {
            for (int i = depth; i < arr.length; i++) {
                swap(arr, i, depth);
                perm(arr, depth + 1, k, primeList);
                swap(arr, i, depth);
            }
        }
    }
 
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    public void returnNumber(int[] arr, int k, Set primeList) {
        int resultNumber = 0;
        for (int i = 0; i < k; i++) {
            resultNumber += arr[i] * Math.pow(10,k-1-i);
        }
        System.out.println(resultNumber);
        
        prime(primeList, resultNumber);
    }
 
    private void prime(Set primeList, int resultNumber) {
        boolean isPrime = true;
        if (resultNumber <= 1) {
            return;
        }
        for (int j = 2; j <= Math.sqrt(resultNumber); j++) {
            if (resultNumber % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primeList.add(resultNumber);
        }
    }
}

 

 

참고

- 순열 알고리즘에 대한 이해 : https://gorakgarak.tistory.com/522

- 완전탐색에 대한 내용 : https://brenden.tistory.com/10