[Algorithm] 프로그래머스_소수 찾기_완전탐색(순열 알고리즘 사용)

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

소수 찾기

[문제 설명]

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

각 종이 조각에 적힌 숫자가 적힌 문자열 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은 같은 숫자로 취급합니다.

 

---

 

풀이 과정

이 문제는 순열 알고리즘과 소수 알고리즘, 해쉬를 이용하였습니다.

 

1. 입력받은 string문자를 string배열에 한 글자씩 담는다.

 

2. 순열을 구하는 메소드를 만들고 입력값의 길이만큼 반복문으로 메소드를 호출한다.

* 순열의 기호는 nPr로 여기서 'r'의 값을 반복문으로 1부터 'n'의 길이만큼 1씩 증가하도록 하였다.

 

3. 소수를 구하여 true, false로 판별해주는 메소드를 만든다.

 

4. 순열의 경우의 수를 전부 구하면서 depth가 end와 같아지면 소수를 구하를 구하는 메소드를 호출하여 참, 거짓으로 판별하여 참일 경우 전역변수의 totalCnt값을 1씩 증가 시켜주었다.

 

5. 중복값이 나올 경우를 대비해서 위 4번에서 구해지는 값마다 해쉬맵에 담는다.

* getOrDefault메소드를 사용하여 1이상 일 경우 중복으로 판단한다.

 

6. 나머지 제한조건의 대한 예외처리를 해준다.

* ex. 0 / 1 / 001 / 0000 등... 이러한 값들을 처리해야 한다.

 

 

풀이

import java.util.HashMap;

class Solution {
    
    int totalCnt = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    
    // 소수 판별 메소드
    boolean isPrime(int num){
        for(int i=2; i*i<=num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }
    
    // 순열 구하는 메소드 (재귀)
    void Permutation(String[] numArr, String[] resultArr, boolean[] visited, int depth, int end){
        int len = numArr.length;  
        if(depth == end){
            String temp = "";
            for(String x : resultArr) {
                temp += x;
            }
            // 가공 전 앞자리 '0' 체크
            while(temp.length() > 1 && temp.charAt(0) == '0'){
                temp = temp.substring(1);
            }
            // 가공 후 앞자리 '0' 체크
            if(temp.equals("0") || temp.equals("1")) return;
            int resultNum = Integer.parseInt(temp);         
            
            // 해쉬로 중복 체크
            map.put(resultNum, map.getOrDefault(resultNum, 0)+1);
            if(map.get(resultNum) == 1){
                if(isPrime(resultNum)){
                    totalCnt++;
                };
            }
            return;
        }else{
            for(int i=0; i<len; i++){
                if(visited[i] == false){
                    visited[i] = true;
                    resultArr[depth] = numArr[i];
                    Permutation(numArr, resultArr, visited, depth+1, end);
                    visited[i] = false;
                }
            }
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        int len = numbers.length();
        String[] numArr = new String[len]; // 입력받은 string을 담기 위한 배열

        for(int i=0; i < len; i++){
            numArr[i] = String.valueOf(numbers.charAt(i));
        }
        
        for(int i=0; i<len; i++){ // 길이 len만큼 순열을 재귀로 구한다.
            String[] resultArr = new String[i+1]; // 순열 결과를 담을 배열 (기호 nPr 생각해본다)
            boolean[] visited = new boolean[len]; // 인덱스 값 사용 여부 체크 배열
            Permutation(numArr, resultArr, visited, 0, i+1);
        }
        
        answer = totalCnt;
        
        return answer;
    }
}

---