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

2020-01-15

소수 찾기 (programers > lev2 > 완전탐색)

문제 링크

문제설명

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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.*;

class Solution {
    
    static ArrayList<Integer> list = new ArrayList<Integer>();
    static int answer = 0;
    static public void swap(int arr[], int depth, int i){
        int temp = arr[depth];
        arr[depth] = arr[i];
        arr[i] = temp;
        
    }
    
    static public boolean sosu(int n){
        boolean chk = true;        
        
        if(n == 1 || n ==0)
            ;
        else{
            for(int i=2;i<n;i++){
                if(n%i == 0){
                    chk=false;
                    break;
                }
            }
            if(chk==true)
                return true;
        }
        
        return false;
    }
    
    static public void perm(int arr[], int depth, int n, int r){
        
        if(depth == r){ //기저조건
            String a = "";
            for(int i=0;i<r; i++)
                a = a + arr[i];
            
            int num = Integer.parseInt(a);
            if(!list.contains(num)){
                list.add(num);
                if(sosu(num))
                    answer++;
            }
            
            return ;
        }
        
        
        for(int i=depth; i<n;i++){
            swap(arr,depth,i);
            perm(arr,depth+1,n,r);
            swap(arr,depth,i);
        }
        
    }
    
    static public int solution(String numbers) {
        int arr[] = new int[numbers.length()];

        for(int i=0; i<numbers.length(); i++)
            arr[i] = Integer.parseInt(String.valueOf(numbers.charAt(i)));
        
        for(int i=1;i<=numbers.length();i++)
            perm(arr,0,numbers.length(),i);
        
        return answer;
    }

    
    
    
    static void main(String args[]){
        System.out.println("hello world");
    }
}


후기 (2h -> 20min)

순열로 나올 수 있는 숫자를 다 만든 후에, 소수를 찾고 소수가 되면 an++ 해주면 되는 문제였는데 오랜만의 순열과 오랜만의 소수.. 문제에 머리가 깜깜해졌다…

그래도 순열 복습했고, 소수도 복습했다!

푼 후에 바로 풀어도 20분이 걸리는 매직.. 복습 철저히 해야 그나마 3,40분 컷 할 수 있지 않을까 싶다….!



tip

  1. permutation - 순열 - nPr - 중복을 허락한다. [1,1,2] 의 경우 [0,2]와

[1,2]를 다른 값으로 취급 한다.

  1. 따라서 중복되는 수들은 list.contains로 확인해 줘야 했다.
  2. 소수 - 1과 자기자신으로만 나누어 떨어지는 수.
  3. 따라서 n은 (2~n-1)까지 나누어 보며 소수가 되는지 확인해야 한다.