프로그래머스 - 소수찾기

https://programmers.co.kr/learn/courses/30/lessons/42839#qna

프로그래머스

 

프로그래머스 소수찾기 문제를 풀었습니다.

테스트케이스 4번이 에러가 나서 정답은 아니지만 더 이상 이 문제를 풀기 싫기 때문에 포스팅하고 추후에 다시 한번 풀어보겠습니다.

이 문제를 처음 접하고는 문제의 풀이 순서를 아래와 같이 정하였습니다.

1. 나올 수 있는 모든 순열을 만들기

2. 순열에 대한 소수 판별을 적용

3. 11 == 011이므로 이와 같은 맨 앞의 0이 들어가는 숫자 처리

순열을 만드는 방법은 아래 출처에 있는 블로그 글을 참조했습니다.

순열을 바로 구현할 수 있는 것이 중요한데, 저의 경우 아직 많이 부족한 것 같습니다.

import java.util.LinkedList;
import static java.lang.Math.sqrt;

public class decimal {
     static class Solution {
        public int solution(String numbers) {
            int answer = 0;

            char[] numberArr = numbers.toCharArray();
            int[] arr = new int[numberArr.length];


            for(int i=0; i<arr.length; i++){
                arr[i] = Integer.parseInt(String.valueOf(numberArr[i]));
            }

            LinkedList<String> permArr = new LinkedList();
            int n = arr.length;
            for(int i=1; i <= arr.length; i++){
                permutation(arr, 0, n, i, permArr);
            }

            answer = permArr.size();
//            System.out.println(answer);
            return answer;
        }

         boolean searchDecimal(int number){

             if( number == 1 || number == 0){
                 return false;
             }

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

         void permutation(int[] arr, int depth, int n, int k, LinkedList permArr){
             if(depth == k){
                 String temp = "";
                 temp = print(arr,k);
                 if(searchDecimal(Integer.parseInt(temp))){
                     for(int i=0; i<temp.length(); i++){
                         if(temp.charAt(0) == '0'){
                             temp = temp.substring(1);
                         }
                     }
                     if(!permArr.contains(temp)){
                         permArr.add(temp);
                         System.out.println(temp);
                     }
                 }
                 return;
             }

             for(int i=depth; i<n; i++){
                 swap(arr, i, depth);
                 permutation(arr, depth+1, n, k, permArr);
                 swap(arr, i, depth);
             }

             return;

         }

         void swap(int[] arr, int i, int j){
             int temp = arr[i];
             arr[i] = arr[j];
             arr[j] = temp;
         }

         String print(int[] arr, int k){
             StringBuilder temp = new StringBuilder();
             for(int i=0; i<k; i++){
                 temp.append((arr[i]));
             }
             return temp.toString();
         }
    }

}

 

출처 : https://gorakgarak.tistory.com/522

순열(Permutation) 알고리즘