[프로그래머스 : 레벨2] 소수 찾기 : 재귀호출 (Java)

이번 문제는 재귀호출을 사용하여서 문제를 풀이하였다. 

문제 자체는 그렇게 어렵지 않았던것 같았는데 풀이과정을 생각해내는데까지 시간이 오래걸렸다.

아무래도 내스스로 재귀호출을 만들어보는게 처음이라 그런지 조금 어려웠다.

 

 

 

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

 

numbers	return
"17"	3
"011"	2

 

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

 

 

위문제에서 아마 제일 어려웠던 부분이 조합의 수를 찾아내는 부분일것 같다.

나는 조합의 수를 찾아내는데 재귀호출을 사용하였다.

 

방법은 글로 설명하기는 어려울수 있으니 보기 쉽게 표를 통하여서 설명하겠다.

 

 

 

위 그림처럼 5를 먼저 방문을 해서 소수인지 확인을 하고 소수를 확인을 하면 HashSet에 넣는다

그리고 숫자 5에 해당하는 부분에 "n" 이라는 값을 넣고

새롭게 업데이트된 {n, 4, 3, 7} 와 숫자 5 그리고 소수를 담는 HashSet을 

재귀함수 호출의 인자로 넣어서 호출한다.

 

public void countPrime(String[] temp, String num, HashSet<Integer> count)

위 함수에서는 

전달 받은 배열에서 n이 아닌 숫자에 각각 접근을 하여서 그 숫자와 전달받은 5를 합쳐서 소수인지 아닌지 확인한다.

 

그래서 54가 소수인지 확인하고 54의 길이가 배열의 길이인 4가 아니라면 

이번엔 54와 {n, n, 3, 7}, HashSet을 담아서 다시 호출한다.

 

그러면 다시 전달 받으면 위에서 했던것을 숫자의 길이와 배열의 길이가같아질때까지 하고. 다 하게 되면 다음걸로 넘어가서 최종적으로는 첫 숫자가 5일때 방문하는곳은 아래와 같아진다.

 

53으로 시작하는건 54가 했던데로 똑같이 한다.

 

그래서 소스를 보면 아래와 같이 나온다.

 

import java.util.HashSet;

public class PreTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();
		
		String str1 = "17";
		String str2 = "011";
		
		System.out.println(p.solution(str1) + "개");
		
		
	}
	
    public int solution(String numbers) {
        int answer = 0;
        
        //1. 문자열을 한자리수로 잘라서 배열에 담기
        String[] su = numbers.split("");
        
        //2. 소수 세는 함수 호출
        answer = countPrime(su);
        
        return answer;
    }
    
    private int countPrime(String[] su) {
		// TODO Auto-generated method stub
    	
    	//소수를 담을 HashSet, 중복 제거를 위해서 사용
    	HashSet<Integer> count = new HashSet<>();
    	
    	//각각의 자리수에 접근
    	for(int i = 0; i<su.length;i++) {
    		
    		//배열복사, 이유는 확인처리를 할때 이전 것들은 남아있지 않게 하기 위해서
    		String[] temp = su.clone();
    		
    		//해당 값이 소수인지 확인
    		if(checkPrime(temp[i])) {
    			count.add(Integer.parseInt(temp[i]));
    		}
    		
    		//그다음에 할것은 이제 값을 확인한것들은 "n"으로 바꿔주고 재귀호출
    		String num = temp[i];
    		temp[i] = "n";
    		countPrime(temp,num,count);
    	}
    	//set 크기를 리턴함으로써 소수개수 보냄
    	return count.size();
	}

	public void countPrime(String[] temp, String num, HashSet<Integer> count) {
		// TODO Auto-generated method stub
		
		//전달받은 배열에 대한 접근
		for(int i = 0; i< temp.length;i++) {
			
			//받은배열에소 "n"으로 표시된애들이 있다면 continue
			if(temp[i].equals("n")) {
				continue;
			}else {//아니라면
				//매개변수로 받은 수를 변수에 저장
				String checkNum = num;
				
				//해당 변수에 n이 아닌값을 더함
				checkNum += temp[i];
				
				//더한 값이 소수인지 아닌지 확인한다.
				if(checkPrime(checkNum)) {
					count.add(Integer.parseInt(checkNum));
				}
				//더한 값의 길이가 배열의 길이보다 짧다면 재귀호출
				if(checkNum.length()<temp.length) { //길이보다 적으면 진입
					//배열 복사해서 복사한 배열에 확인처리 후 확인처리한걸 재귀호출시 사용
					String[] temp2 = temp.clone();
					temp2[i] = "n";
					countPrime(temp2,checkNum,count);
				}else {
					break;
				}
			}	
		}
	}

	//주어진 수가 소수인지 아닌지 확인 소수이면 true 아니면 false
    public boolean checkPrime(String num) {
    	
    	boolean flag = true;
    	
    	int su = Integer.parseInt(num);
    	if(su<=1) {
    		flag = false;
    	}else {
    		for(int i = 2; i<su;i++) {
    			if(su%i == 0) {
    				return false;
    			}
    		}
    	}
        return flag;
    }
}

 

내가 처음에는 테스트케이스 2,8에 시간초과가 떴는데 그 이유를 알고보니 소수를 구하는 부분에서 생겼다.

소수는 해당 수이전의 수로 계속해서 나눴을때 나눠 떨어지는 거였는데 내가 생각을 잘못했다.

 

위문제를 내가 DFS를 배우고 나서 좀더 다른 방식으로 문제를 풀어봤다.

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		PreTest p = new PreTest();

		String numbers = "1523";

		System.out.println(p.solution(numbers));

	}


    
    public int solution(String numbers) {
        int answer = 0;
        
        String[] num = numbers.split("");
        boolean[] visit = new boolean[num.length];
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i< num.length;i++){
            dfs(i,num[i],visit,num,set);
            visit[i] = false;
        }
        answer = set.size();
        return answer;
    }
    
    public void dfs(int index, String num, boolean[] visit, String[] numbers, HashSet<Integer> set){
    	visit[index] = true;
    	if(checkPrime(num)) {
    		int su = Integer.parseInt(num);
    		set.add(su);
    		System.out.println(set);
    	}
    	if(num.length() == numbers.length)
    		return;
    	for(int i = 0; i<numbers.length;i++){
        	if(!visit[i]) {
        		dfs(i,num+numbers[i],visit,numbers,set);
        		visit[i] = false;
        	}
        }
    }
    
    public boolean checkPrime(String num){
        int su = Integer.parseInt(num);
        boolean flag = true;
        if(su <= 1){ //1이하는 소수 아님
            return false;
        }
        for(int i = 2; i<su;i++){
            if(su%i == 0){ //나눴을때 나눠지면 소수아님
                return false;
            }
        }
        
        return flag; //true로 계속 남으면 소수임
    }

처음에 내가 풀었던 방식과는 크게 달라지는것음 없는데 불필요한 부분을 없애고 그렇게했다.

 

 

느낀점

1. 문제를 차근차근히 단계별로 생각하면 금방 풀수있다.

2. 시간복잡도를 항상 생각하자.

3. HashSet은 중복제거가 된다.(제거라기보단 중복이면 중복저장을 안함)