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

 

문제

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42840

코딩테스트 연습 - 모의고사

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

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

제한사항

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

입출력 예

numbers	return
17	3
011	2

 

풀이

2가지 문제로 나눠서 생각할 수 있다.

1. 주어진 숫자로 모든 순열 만들기 (진부분집합 만들기)
2. 숫자를 소수 판별하기

우선 조합을 만드는 방법은 다음과 같다.

재귀함수를 사용하여 순열을 만들었는데,

스왑을 통해서 선택된 것을 앞으로, 안된것들을 뒤로 몰아넣은 뒤 ,

원하는 깊이만큼 (nPr에서 r) 재귀호출해서 뽑아주는 방식이다.

ex) 1 2 3 에서 2개

depth = 0, i = 0에서 1선택

​ -> depth = 1, i=1에서 2 선택 (1,2) or depth = 1, i = 2해서 3선택 (1,3)

depth = 0, i = 1에서 2선택 후 swap (2,1,3)

​ -> depth = 1, i = 1에서 1선택 (2,1) or depth = 1, i = 2 해서 3선택 (2,3)

depth = 0, i =2 에서 3선택 후 swap(3,1,2)

​ -> depth = 1, i = 1에서 1선택 (3,1) or depth = 1, i = 2 해서 3선택 (3,2)

소수임을 판별하는 방법은, 이전에 알고리즘 과제로 했던 것을 사용했다 (사실 틀렸어서 고쳤다.)

1. 2와 3이면 소수
2. 1이나 짝수면 소수x
3. 3부터 홀수번 을 i*i < n 개 체크 -> 이때 3의 배수를 중복해서 세어주지 않게 변수를 넣어서 조절해주기.

시간복잡도는 모든 부분집합을 만드는데 $O(2^{N})$, 중복인지 확인하는데 $O(2^{N})$소수판별하는데 $O(\sqrt{N})$ 으로 $O(2^{2N}\sqrt{N})$이다

 

코드

import java.util.ArrayList;

public class Main {
	public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static void main(String[] args)throws Exception {
    	Solution s = new Solution();
    	System.out.println(s.solution("919"));
    }
}
class Solution {
	ArrayList<Integer> subArrayList = new ArrayList<Integer>();
	
	public int solution(String numbers) {
        int answer = 0;
        int[] res;
        int[] num = new int[numbers.length()];
        int i=0;
        
        for(char c : numbers.toCharArray()) {
        	num[i++] = Character.getNumericValue(c);
        }
        
        
        for(i=1; i<=num.length; i++) {
        	res = new int[i];
        	//조합으로 arraylist 채움.
        	perm (res,num.length, res.length, num, 0);
        }
        System.out.println(subArrayList);
        
        for(i=0; i<subArrayList.size(); i++) {
    		if(DetectPrime(subArrayList.get(i))) {
    			System.out.println(subArrayList.get(i));
    			answer++;
    		}
    			
    	}
        return answer;
    }
	
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    public void perm(int[] res, int n, int r, int[] arr, int depth) {
        
        // depth가 0부터 시작했을 경우 depth == r에서 리턴
        if (depth == r) {
            String s = "0";
            
            for(int i=0; i<res.length; i++) {
            	s = s + Integer.toString(res[i]);
            }
            
            int a = Integer.parseInt(s);
            for(int i=0; i<subArrayList.size(); i++) {
            	if(subArrayList.get(i) == a) return;
            }
            subArrayList.add(a);
            return;
        }
        
        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);     // 스왑
            res[depth] = arr[depth]; // 선택된 원소 저장
            perm(res, n,r, arr, depth +1);     // 재귀호출
            swap(arr, depth, i);     // 복원
        }
    }
    
    public boolean DetectPrime(int num) {
    	
    	if(num == 2 || num == 3) {
    		return true;
    	}
    	//1이나 짝수면
    	if(num == 1 || num % 2 ==0) {
    		return false;
    	}

    	boolean check = true;
    	int k = 4;
    	for(int i=3; i*i <= num; i=i+2) {
    		k--;
    		if(k==0) { //큰 수에서 3이 중복되어 계산되지 않게
    			k=3;
    			continue;
    		}
    		if(num%i ==0) {
    			check =false;
    			break;
    		}
    		
    	}
    	return check;
    }
}

 

결과