[코딩테스트] 프로그래머스 42839, 소수 찾기

문제

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

프로그래머스

 

문제접근

• 각각의 숫자를 이용하여 순열로 표현할 수 있는 수를 탐색합니다.
  • 예를 들어 "123"이라는 문자열을 입력받았을때 표현할 수 있는 순열은 다음과 같습니다.
  • 아래는 3P1 + 3P2 + 3P3 = 3 + 6 + 6 = 15로 계산할 수 있습니다.

1
2
3
12
21
13
31
23
32
123
132
213
231
312
321

• 어떤 특정한 수를 찾았다면 그 수가 소수인지 판단하고 소수이고 결과 집합에 포함되어 있지 않은 수라면 카운트합니다.

 

구현

import java.util.*;

public class Solution{
	static int answer = 0;
	static Set<Integer> set = new HashSet<>();
	public boolean isPrime(int n){
		if(n < 2){
			return false;
		}

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

	public void permutation(int n, int r, List<Integer> perArr, boolean[] perCheck, int[] arr){
		if(perArr.size() == r){
			String s = "";
			int target = 0;
			for(int i : perArr){
				s += i;
			}
			target = Integer.parseInt(s);
			if(isPrime(target) && !set.contains(target)){
				set.add(target);
				answer++;
			}
			return;
		}
		for(int i = 0; i < n; i++){
			if(!perCheck[i]){
				perArr.add(arr[i]);
				perCheck[i] = true;
				permutation(n, r, perArr, perCheck, arr);
				perCheck[i] = false;
				perArr.remove(perArr.size()-1);
			}
		}
	}
	
    public int solution(String numbers) {

		int[] arr = Arrays.stream(numbers.split("")).mapToInt(Integer::parseInt).toArray();
		int n = arr.length;
		answer = 0;

		for(int i = 1; i <= n; i++){
			List<Integer> perArr = new ArrayList<>();
			boolean[] perCheck = new boolean[n];
			permutation(n, i, perArr, perCheck, arr);
		}

		return answer;

    }
    
	public static void main(String args[])
	{
		String numbers = "011";
		int answer = new Solution().solution(numbers);
		System.out.println(answer);
	}
}

 

References

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽
Permutation Algorithm(순열 알고리즘) & Combination Algorithm(조합 알고리즘)