[프로그래머스] 완전탐색 - 소수찾기 (조합)

프로그래머스 2단계 완전탐색 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/42584?language=java

문제설명

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

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

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다.

013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

prices	return
17	3

입출력 예 설명

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

자바코드

           
import java.util.*;
class Solution {
    public static boolean[] prime() {
		boolean[] primes = new boolean[10000000];
		primes[0] = primes[1] = true;
		for(int i = 2; i < primes.length; i++) {
			if(!primes[i]) {
				for(int j = 2; j * i < primes.length; j++) {
					primes[j * i] = true;
				}
			}
		}
		
		return primes;
	}
	
	public static int solution(String numbers) {
        int answer = 0;
        int[] arr = new int[numbers.length()];
        for(int i = 0; i < arr.length; i++) 
        	arr[i] = numbers.charAt(i) - '0';
        
        Set set = new HashSet<>();
        for(int i = 1; i <= arr.length; i++) 
        	permutation(set, arr, 0, i);
        
        boolean[] primes = prime();
        for(int num : set) {
        	answer = primes[num] ? answer : answer + 1;
        }
        return answer;
    }
	
	public static void permutation(Set set, int[] arr, int index, int r){
        if(index == r){
        	set.add(createInteger(arr, r));
        } else {
        	for(int i = 0; i + index < arr.length; i++){
                swap(arr, index, index + i);
                permutation(set, arr, index + 1, r);
                swap(arr, index, index + i);
            }	
        }
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    public static int createInteger(int[] arr, int r) {
    	StringBuilder sb = new StringBuilder();
    	for(int i = 0; i < r; i++) 
    		sb.append(arr[i]);
    	
    	return Integer.parseInt(sb.toString());
    }
}

문제설명

이 문제는 브루트 포스로 풀이 가능한 문제이다. 브루트 포스 모든 경우의 수를 모두 확인하기 때문에 시간복잡도가 높지만 풀이가 단순하다는 장점을 

가지고 있다. 이 문제가 브루트 포스로 가능한 이유는 문자열의 길이가 7이기 때문에 나올 수 있는 경우의 수가 그렇게 많지 않기 때문이다.

이 문제는 두 단계를 통해 풀 수 있다. 첫 단계는 모든 소수를 구하기! 두번째 단계는 조합 알고리즘을 이용해서 모든 경우의 수를 찾기!

그리고 나서는 모든 경우의 수에서 소수가 몇개인지 구하면 된다. 소수는 아마 모두 구할 수 있을 것이다! 하지만 조합은 만만치가 않다.

그래서 조합과 순열에 대한 코드를 아래 적어보았다. 풀이는 주석을 통해 간단하게 작성되있다!

  
package BOJ;

public class Combination {
    public static void main(String[] ar){
       /* 조합 */
       int n = 5;
       int r = 3;
       int[] arr = {1, 2, 3, 4, 5};
       int[] container = new int[arr.length];
        combination(container, n, r, 0, 0, arr);
        
        /* 순열 */
        permutation(arr, 0);
    }

    /*
        @ param container : 선택한 요소들을 저장하는 배열
        @ param n        : 요소들의 갯수
        @ param r        : 선택할 요소들의 총 갯수 (선택하면 r - 1, 선택하지 않으면 r)
        @ param index     : container 배열의 위치를 나타내는 index
        @ param target    : 선택한 수가 아닌, 선택한 수의 arr 배열에서의 위치
    */
    public static void combination(int[] container, int n, int r, int index, int target, int[] arr){
        if(r == 0){
           // 배열을 모두 탐색하든 탐색하지 않든, r개를 뽑은 경우에는 통과! //
            printArr(arr, container);
        } else if(target == n) {
           // 배열을 모두 탐색했지만, r개를 뽑지 못한 경우에는 통과! //
        } else{
           container[index] = target;
           combination(container, n, r - 1, index + 1, target + 1, arr); 
           combination(container, n, r, index, target + 1, arr); 
        }
    }
    
    public static void printArr(int[] arr, int[] container) {
       for(int i = 0; i < 3; i++) 
          System.out.print(arr[container[i]]);
       
       System.out.println();
    }
    
    public static void printArr(int[] arr) {
       for(int i = 0; i < 3; i++) 
          System.out.print(arr[i]);
       
       System.out.println();
    }
    
    public static void permutation(int[] arr, int index){
        if(index == arr.length - 1){
            printArr(arr);
        } else {
           for(int i = index; i < arr.length; i++){
                swap(arr, index, i);
                permutation(arr, index + 1);
                swap(arr, index, i);
            }   
        }
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}