[프로그래머스(Programmers)][자바(java)] (Lv2) 소수 찾기

 

programmers.co.kr/learn/courses/30/lessons/42839

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

 

문제 설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

 

문제 풀이

 

import java.util.TreeSet;

public class Solution {
	
	TreeSet<Integer> ts;
	
	public void perm( int cnt, int n, int m, int num[], int a[], boolean v[] ) {
		if( cnt == m ) {
			StringBuilder sb = new StringBuilder();
			for( int i = 0; i < m; i++ )
				sb.append( num[a[i]] );
			int res = Integer.parseInt( sb.toString() );
			if( isPrime( res ) )
				ts.add( res );
			return;
		}
		for( int i = 0; i < n; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				a[cnt] = i;
				perm( cnt+1, n, m, num, a, v );
				v[i] = false;
			}
		}	
	}

	public boolean isPrime( int n ) {
		if( n < 2 ) return false;
		int i, m = (int)Math.sqrt(n);
		for( i = 2; i <= m; i++ )
			if( n % i == 0 )
				return false;
		return true;
	}
	
	public int solution( String numbers ) {
		int len = numbers.length(), i;
		int num[] = new int[len];
		for( i = 0; i < len; i++ )
			num[i] = numbers.charAt(i)-'0';
		ts = new TreeSet<>();
		int arr[] = new int[len];
		boolean visited[] = new boolean[len];
		for( i = 1; i <= len; i++ ) 
			perm( 0, len, i, num, arr, visited );
		return ts.size();
	}

}

 

문자열로 구성된 숫자들을 int 배열로 만든 후 순열을 구해 소수인 수만 TreeSet에 넣음 ( 중복 제거를 위해 )

TreeSet의 사이즈가 소수의 개수가 됨