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

문제보러가기

코딩테스트 연습 - 소수 찾기

이문제는 완전 탐색 문제로 주어진 숫자로 만들 수 있는 모든 문자 중에 소수를 찾는 문제였다. 숫자로 순열을 만드는 코드를 작성할 수 있다면 쉽게 풀 수 있었던 문제인 거 같다. (물론 나는 순열 코드를 고치고 결국 참고하고...ㅎ) 공부할게 역시 엄청나게 많구나를 느낀 문제였다 ㅎ...

 

 

-참고한 순열 코드 & 설명                                                                                                                       

 

import java.util.HashSet;
import java.util.stream.Stream;
class Solution {
	//중복된 숫자가 담기지 않게 구하는 숫자를 set에 저장
    static HashSet<Integer> ansSet = new HashSet<>();
    public int solution(String numbers) {
    	//String을 int배열로 넣는 코드
       int[] intNumbers = Stream.of(numbers.split("")).mapToInt(Integer::parseInt).toArray();

        for (int i = 1; i <= numbers.length(); i++) {
        	//1개부터 n개의 숫자를 선택하여 순열생성	
        	permutation(intNumbers,0,numbers.length(),i);
        }
        return ansSet.size();

    }


    static void permutation(int[] arr, int depth, int n, int r) {
        if (depth == r) {
            String checkNum = "";
            for (int i = 0; i < r; i++){
                checkNum = checkNum+arr[i];
            }
            if(isPrime(Integer.parseInt(checkNum))){
                ansSet.add(Integer.parseInt(checkNum));
            }
            return ;
        }

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

    }

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

    static boolean isPrime(int num) {
        if (num == 1 || num == 0)
            return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num != 2 && num % i == 0) {
                return false;
            }
        }
        return true;
    }

}

               

보다 보니 이런 swap을 이용한 코드가 아닌 subString을 이용한 순열 생성 코드도 있길래 가져와보았다!

public void permutation(String prefix, String str, HashSet<Integer> set) {
        int n = str.length();
        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);

    }

 신기하고 재미있으며 어렵기도 한 코드의 세계,,,,,ㅎ