[프로그래머스] 소수 찾기_순열 구하기

문제 링크 :
https://school.programmers.co.kr/learn/courses/30/lessons/42839

코드를 알아보기 전에 먼저 문제와 알고리즘을 이해하여 스스로의 힘으로 코드를 짜보는 시간을 갖길 바랍니다.

문제 이해하기

문제의 이름은 '소수 찾기'이지만, 이 문제에서 가장 중점적인 문제는 소수를 판별하는 것이 아닌 '순열 구하기'입니다.

주어진 숫자 조각들을 순서에 상관 있게 1개에서 숫자 조각의 갯수만큼 뽑은 후 해당 숫자 조각들을 하나의 숫자로 보았을 때 해당 숫자가 소수인지 아닌지를 판별해야 하기 때문이죠.

순열을 구현하고자 할 때 모든 숫자 조각을 참고해 순열을 구해야 하므로 순열을 구하는 문제는 완전탐색 문제이기도 합니다.

완전탐색 문제를 푸는 방법은 다양하지만, 순열을 구현하기 위해선 DFS(Depth First Search)에 백트래킹을 접목한 알고리즘을 많이 이용합니다.

알고리즘 이해하기

• 순열 구하기
  전제 조건 : 조각의 갯수가 n개이고 그 중 r개를 순서에 상관 있게 뽑아 결과 배열에 넣는다.

1. 조각 배열에서 하나를 무작위로 선택한다.
2. 선택한 조각은 해당 조각의 배열 상 위치에 뽑았음을 표시한다.
3. 결과 배열의 0(i가 0)번째 위치에 선택한 조각을 넣는다.
4. 뽑지 않은 조각 중 하나를 무작위로 선택한다.
5. 선택한 조각이 뽑혔음을 표시하고 결과 배열의 i+1번째 위치에 선택한 배열을 넣는다.
6. 3-4 과정을 결과 배열이 다 채워질 때까지(i가 r과 같아질 때까지) 반복한다.
7. 하나의 순열을 완성했다면 뽑은 조각은 뽑지 않았음으로 변경한다.

• 소수 구하기

1. 숫자 i를 2부터 i/2까지 나눠 나머지가 0으로 떨어지는지 확인한다. 이때, 나누어 떨어지면 소수가 아니다.
2. 끝까지 한 번도 나누어 떨어지지 않았다면 소수이다.

tip

• 중복되는 숫자를 주의하세요!
• 맨 앞에 0이 오는 숫자는 반드시 중복이므로 무시해야 합니다.
• 짝수인 소수는 2가 유일합니다.

문제 해결 코드(java)

import java.util.*;

class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    int answer = 0;
    
    public int solution(String numbers) {
        
        for(int i = 1; i <= numbers.length(); i++){
            perm(numbers.split(""), new String[i], new boolean[numbers.length()], 0);
        }
        
        //System.out.println(list);
        
        return answer;
    }
    
    void perm(String[] pieces, String[] result, boolean[] choiced, int th) {
        if (th == result.length) {
            String str = String.join("", result);
            int a = Integer.valueOf(str);
            
            if(!list.contains(a) && primeNumber(a)) {
                list.add(a);
                answer++;
            }
            return;
        }

        for (int i=0; i < pieces.length; i++) {
            if(th == 0 && pieces[i].equals("0")) continue;
            if (choiced[i] != true) {
                choiced[i] = true;
                result[th] = pieces[i];
                perm(pieces, result, choiced, th + 1);       
                choiced[i] = false;
            }
        }
    }
    
    boolean primeNumber(int i){
        if(i < 2) return false;
        
        for(int j = 2; j <= i/2; j++){
            if(i % j == 0) return false;
        }
        
        return true;
    }
}

출력 내용

예제로 주어진 값으로 출력했을 때 아래의 결과를 볼 수 있습니다.

결과적으로 어떤 소수들이 존재하는지 확인하기 위해 구현한 것이므로 반드시 구현할 필요는 없습니다.

[7, 17, 71]