[Algorithm] 프로그래머스 - 소수찾기

https://www.welcomekakao.com/learn/courses/30/lessons/42839?language=java

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

문제를 보면...숫자를 몇개 줄테니 주어진 각각의 숫자에 대해 조합을 해서 만들어진 숫자가 소수가 맞으면 그 카운트를 세서 return하는 문제이다.

 

먼저 컨셉을 잡자..

 

뭔가 숫자를 가지고 뽑고 순서를 고려하며 나열을 해야한다. 그렇다. 순열이다.

1. 순열을 구하는 함수!

다음 해당 순열로 만들어진 숫자가 소수인지 판단해야한다. 

2. 소수인지 아닌지 판별하는 함수!

 

크게 2가지 로직을 짜면 위 문제는 쉽게 풀 수 있다.

 

다만, 한가지 팁을 주자면..성능적인 측면에서 순열을 하다보면 중복되는 숫자가 나오게 되고 이미 검사했던 숫자에 대해 소수 판별 로직을 태우게 되면 시간이 오래 걸린다.
따라서, 이력관리를 하는 배열을 하나 선언해두고 미수행, 수행에 대한 기록을 남기게 해서 만약 미수행인 숫자인 경우에만 소수 판별 로직을 태우게 되면 성능적인 부분에서 효과를 볼 수 있다.

 

 

import java.util.LinkedList;

class Solution {
    static int numberArray[];
    static int ans[] = new int[9999999];
    static int answer = 0;
    public int solution(String numbers) {
       numberArray = new int[numbers.length()];
        for(int i=0; i<numberArray.length; i++){
            numberArray[i] = Integer.parseInt(numbers.charAt(i)+"");
        }

        int n = numberArray.length;
        for(int i=1; i<=numberArray.length; i++){
            LinkedList<Integer> perArr = new LinkedList<Integer>(); 
            int[] perCheck = new int[n];
            permutation(n, i, perArr, perCheck);
        }

        return answer;
    }

    //순열 (순서있게 배열)
	private static void permutation(int n, int r, LinkedList<Integer> perArr, int[] perCheck) {
			if(perArr.size() == r){
				String tmpNum ="";
				for(int i : perArr){
					//System.out.print(numberArray[i]+" ");
					tmpNum += numberArray[i]+"";
				}
				
				if(ans[Integer.parseInt(tmpNum)] == 0){
					//소수 판별 로직 수행
					// 0 미수행, 1소수아님, 2소수임
					if(checkPrime(Integer.parseInt(tmpNum)) == 2){
						answer++;
					}
				}
				//수행
				ans[Integer.parseInt(tmpNum)] = 1;
				
				return;
			}
			
			for(int i=0; i<n; i++){
				if(perCheck[i] == 0){
					perArr.add(i);
					perCheck[i] = 1;
					permutation(n, r, perArr, perCheck);
					perCheck[i] = 0;
					perArr.removeLast();
				}
			}
			
	}
	
	//소수인지 아닌지 체크하는 함수
	private static int checkPrime(int num) {
		//1,0은 소수가 아님
		if(num == 1 || num == 0)return 1;
		for(int i=2; i<num; i++){
			if(num%i == 0){
				//소수가 아님
				return 1;
			}
		}
		//소수임
		return 2;
	}
}