프로그래머스 42839번 (순열 문제)

일단 문제를 통해서 어떤 방식으로 접근했는지 살펴보자.

 

 

프로그래머스 42839번 소수찾기 문제이다.

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 numbersreturn 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다. 11과 011은 같은 숫자로 취급합니다.

 

먼저 문제를 읽고 3단계를 거쳐서 풀어나갈 생각을 했다.

 

1. 입력 받은 numbers의 문자열을 하나씩 배열에 담아 만들어 낼 수 있는 모든 값을 먼저 찾자

 

2. 그 값들이 소수인지 판별을 하자

 

3.소수라면 값을 저장하고 저장된 값의 길이를 출력하자.

 

그런데 1번을 해결하기 위해서는 순열을 알고 있어야 한다. 중학교때 공부했던 순열과 조합을 다시 살펴보자.

 

순열

순열이란 n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말합니다.

예를 들어 [1, 2, 3] 있다면

 

3 개의 배열에서 1 개의 숫자를 뽑는 경우는  : 3P1 : 3가지

[1]

[2]

[3]

 

3 개의 배열에서 2 개의 숫자를 뽑는 경우는 3P2 : 3*2 가지

[1, 2]

[1, 3]

[2, 1]

[2, 3]

[3, 1]

[3, 2]

 

3 개의 배열에서 3 개의 숫자를 뽑는 경우는 3P3 : 3*2*1 가지

[1,2,3]

[1,3,2]

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

 

 

 

문제에서 주어진 1,7의 값을 통해 모든 순열을 구하면

1, 7 , 17 , 71 

4가지가 나오고 이 값들의 소수를 판단하면 끝~

 

 

 

package codingtest;

import java.util.HashSet;

public class L_42839 {
	
	
	 public int solution(String numbers) {
		 int answer = 0;
		 HashSet<Integer> hs = new HashSet<Integer>(); //소수 저장
		 
         //String -> int형 배열에 넣고
		 String[] ch = numbers.split("");
		 int[] arr = new int[ch.length];
		 int k =0;
		 
		 for (String string : ch) {
			arr[k]=Integer.parseInt(string);
			k++;
		}
		
		//모든 순열을 호출
	    for (int i = 1; i <= arr.length; i++) {
	    	permutation(arr, 0, arr.length, i, hs);
		}
	    
	    answer = hs.size();
	    return answer;
	}
	 
	 
	 //순열 가져오기
	 static void permutation(int[] arr, int depth, int n, int r, HashSet<Integer> hs) {
	    if(depth == r) {
	    	String k = "";
	        for(int i=0; i<r; i++) {
	            k = k + arr[i];
	        }
	        //소수 판별 , hs에 소수값 담기
	        sosuCheck(Integer.parseInt(k),hs);
	        
	        return;
	    }
	 
	    for(int i=depth; i<n; i++) {
	        swap(arr, depth, i);
	        permutation(arr, depth + 1, n, r, hs);
	        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 void sosuCheck(int k , HashSet<Integer> hs) {
		int n = 2;
		//사용자의 입력값을 대상으로 
		//나눗셈 연산을 수행할 변수(1씩 증가 예정) 
		boolean flag=true; 
		//--소수다~!!!(check~!!!) 
		while(n<k) { 
			if(k%n==0) { 
				flag = false; //-- 소수가 아니다~!!! 
				break; 
			} 
			n++;
		}
		
        //소수라면
		if(flag == true && k != 1 && k != 0) {
			hs.add(k);
		}


	}
	 

	 
	 
	 
	public static void main(String[] args) {
		L_42839 l = new L_42839();
		l.solution("011");
	}

}

 

numbers numbers