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

프로그래머스 level2 소수찾기

 

소요시간 : 40분

 

문제 대충 읽어서 시간이 더 걸렸다...ㅋ

 

subset으로 숫자 선택 후 선택된 숫자들을 permutation 돌려서 순서 바꾸고,

소수인지 2부터 자신-1 수까지 다 나눠보고 소수이면 set에 넣어 중복방지 해줬다..

 

풀고나서 다른 사람들 코드 보니 substring 으로 막 깔끔하게 했던데 아직 이해하지 못했다. ㅎ

그리고 미리 짝수 같은 건 코드 안 돌게 방지하면 좋을 듯하다.

 

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
	int N;
	char[] nums;
	boolean[] selected;
	List<Integer> list;
	int answer = 0;
	Set<Integer> set = new HashSet<>();
	
	public int solution(String numbers) {
		N = numbers.length();
		selected = new boolean[N];
		nums = numbers.toCharArray();
		
        subset(0);
        return set.size();
    }
	
	public void subset(int cnt) {
		if(cnt == N) {
			list = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				if(selected[i]) continue; 
				list.add(nums[i]-'0');
			}
			
			size = list.size();
			permu_selected = new boolean[size];
			selected_numbers = new int[size];
			permu(0);
			return;
		}
		
		selected[cnt] = true;
		subset(cnt+1);
		selected[cnt] = false;
		subset(cnt+1);
	}
	
	int size;
	int[] selected_numbers;
	boolean[] permu_selected;
	public void permu(int cnt) {
		if(cnt == size) {
			addPrime();
			return;
		}
		
		for (int i = 0; i < size; i++) {
			if(permu_selected[i]) continue;
			permu_selected[i] = true;
			selected_numbers[cnt] = list.get(i);
			permu(cnt+1);
			permu_selected[i] = false;
		}
	}
	
	public void addPrime() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < size; i++) {
			sb.append(selected_numbers[i]);
		}
		
		if(sb.length() != 0) {
			int num = Integer.parseInt(sb.toString());
			if(num == 1 || num == 0) return;
			for (int i = 2; i < num; i++) {
				if(num % i == 0) return;
			}
			set.add(num);
		}
	}
}