[프로그래머스 #level2] 소수찾기.java

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

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

완전탐색

 

모든 경우의 수 를 다 따져봐야 하는 문제이다.

 

크게 2가지 스텝으로 나눴다.

    STEP 1) 조합으로 모든 경우의 수 완전 탐색

    STEP 2) 소수 인지 판별

 

1단계에서 중복된 숫자가 나올 수 있는 경우를 제외해 줘야 한다.

    -. 중복 제거를 위해 SET 자료 구조 활용.

    -. 맨 앞이 0인 경우는 제외!

package eun;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class Eun {
	private static int count;
	private static TreeSet<String> ts = new TreeSet<>();
	
	public static void main(String[] args) {
		String numbers = "011";
		
		System.out.println(solution(numbers));
	}
	
	private static int solution(String numbers) {
		List<Character> origin = new ArrayList<>();
		List<Character> result = new ArrayList<>();
		int n = numbers.length();
		
		for (int i=0; i<n; i++) {
			origin.add(numbers.charAt(i));
		}
		
		for (int i=1; i<=n; i++) {
			recursion(origin, result, n, i);			
		}
		
		int answer = count;
		return answer;
	}
	
	private static void recursion(List<Character> origin, List<Character> result, int n, int pick) {
		// 탈출
		if (pick == 0) {
			// 0으로 시작하는거 제거
			if (result.get(0) == '0') return;
				
			// result에 담긴 결과 String화
			String strResult = "";
			for (char c : result) {
				strResult += c;
			}
			
			// 중복 되지 않으면
			if( !ts.contains(strResult) ) {
				// 결과에 추가하고
				ts.add(strResult);
				
				// 소수 판별
				if ( isPrime(Integer.parseInt(strResult)) ) {
					System.out.println(strResult);
					count++;
				}
			}
			
		}
		
		for (int i=0; i<n; i++) {
			result.add(origin.remove(i));
			recursion(origin, result, n-1, pick-1);
			origin.add(i, result.remove(result.size() -1));
		}
	}
	
	
	// 소수 판별
	private static boolean isPrime(int n) {
		int sqrt = (int) Math.sqrt(n);
		
		// 2는 소수
		if (n == 2) return true;
		
		// 1 또는 짝수는 소수가 아님
		if (n == 1 || n%2 == 0) return false;
		
		// 제곱근까지만 홀수로 나눠보면 됨
		for (int i=3; i<=sqrt; i +=2) {
			if ( n%i ==0 ) return false;
		}
		
		return true;
	}
}