[순열] 소수찾기

프로그래머스 완전탐색>소수찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?language=java

1. 처음 짠 소스

import java.util.ArrayList;
import java.util.List;

class Solution {
    static List<Integer> primeNum = new ArrayList<>();

    public static int solution(String numbers){

        //문자열을 배열로 바꿈
        int[] numArr = new int[numbers.length()];

        for(int i=0 ; i<numbers.length(); i++){
            numArr[i] = Integer.parseInt( Character.toString( numbers.charAt(i) ) );
        }

        for(int i=1; i<=numArr.length; i++){
            combination(new int[i], 0, numArr.length, i, 0, numArr);
        }
        return primeNum.size();
    }

    //조합
    public static void combination(int[] arr, int index, int n, int r, int target, int[] numArr) {
        if(r==0){
            //숫자완성
//            System.out.println(arr.length + " / " + numArr.length);
            int[] arrCopy = new int[arr.length];
            for(int i=0; i<arr.length; i++){
                arrCopy[i] = arr[i];
            }
            arrangeArr(arrCopy, numArr);
        }
        else if (target==n) return;
        else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1, numArr);
            combination(arr, index, n, r, target+1, numArr);
        }
    }

    public static void arrangeArr(int[] arr, int[] numArr){

        for(int i=0; i<arr.length; i++){
            arr[i] = numArr[ arr[i] ];
        }

        perm(arr, 0, arr.length, arr.length);
    }

    //순열
    public static void perm(int[] arr, int depth, int n, int k) {

        if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
//            System.out.println( arrToint(arr) );
            checkPrime( arrToint(arr) );
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, i, depth);
            perm(arr, depth + 1, n, k);
            swap(arr, i, depth); //원상복귀
        }
    }


    public static void  swap(int[] arr, int i, int depth){
        int temp = arr[i];
        arr[i] = arr[depth];
        arr[depth] = temp;
    }


    public static int arrToint(int[] arr){

        String num = "";
        for(int i=0; i<arr.length; i++){
            num += Integer.toString( arr[i] );
        }
        return Integer.parseInt( num );
    }

    public static void checkPrime(int number){

//        System.out.println(number);

        if(number==0 || number==1) return;

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

        //중복체크 후 삽입
        for(int i=0; i<primeNum.size(); i++){
            if(number == primeNum.get(i)) return;
        }
//        System.out.println("입력:" + number);
        primeNum.add(number);
    }
}

조합을 한 다음 순열을 해서 전체 경우의 수를 구함.

2. 개선된 소스

package com.company;
import java.util.HashMap;
import java.util.Map;

public class PrimeNumber {

    public static void main(String[] args){
        System.out.println("결과: " + solution("17"));
    }


    static Map<Integer, Integer> hash = new HashMap<>();

    public static int solution(String numbers){

        //문자열을 int로 바꿔서 배열에 넣음
        String[] numsStr = numbers.split("");
        int[] nums = new int[numbers.length()];

        for(int i=0; i<numbers.length(); i++){
            nums[i] = Integer.parseInt( numsStr[i] );
        }

        for(int i=1; i<=numbers.length(); i++){
            permutation(nums,0, nums.length,i);
        }
        return hash.size();

    }

    //숫자세트 만들기
    private static void permutation(int[] arr, int depth, int n, int k) {

        if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.

            //arr중 k번째까지가 유효
//            System.out.println( makeIntNumber(arr, k) );
            checkPrime( makeIntNumber(arr, k) );

            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n, k);
            swap(arr, depth, i); //원상복귀
        }
    }

    private static void swap(int[] arr, int i, int depth){
        int temp = arr[i];
        arr[i] = arr[depth];
        arr[depth] = temp;
    }



    //배열의 안의 값을 k번째까지 이어붙여서 숫자로 만듦
    private static int makeIntNumber(int[] arr, int k){
        int result = 0;
        for(int i=0; i<k; i++){
            result += arr[i] * Math.pow(10, i);
        }
        return result;
    }



    //소수인지 체크(에라토스테네스의 체를 이용하여 성능개선 가능)
    public static void checkPrime(int number){

        if(number==0 || number==1) return;

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

        //해쉬에 삽입(똑같은건 덮어씌워져서 중복체크 방지)
        hash.put(number, number);
    }


}

Permutation함수만 이용해서 전체 경우의 수를 구함.

Hash를 써서 중복처리.

3. Permutation

http://gorakgarak.tistory.com/522