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

먼저 주어진 숫자형 문자열로 만들 수 있는 모든 숫자를 찾고 그 다음 만들어진 숫자에서 소수를 골라낸다.

 

"17" 로 만들 수 있는 숫자는 [1, 7, 17, 71] 이고 여기서 소수는 [7, 17, 71]

"011" 로 만들 수 있는 숫자는 [0, 1, 10, 11, 101, 110] 이고 여기서 소수는 [11, 101]

 

그림에서 보는 것 처럼 배열에서 루프를 돌며 숫자를 하나씩 뽑고, 남은 배열을 저장하면서 들고다니는 함수를 만들어서 계속 재귀호출하며 남은 배열이 없으면 전체 조합을 완료한 것으로 본다.

 

public void pick(List<String> arr, String picked, List<Integer> permArr) {

    for (int i = 0; i < arr.size(); i++) {
        // 입력받은 배열에서 하나씩 뽑는다.
        String s = arr.get(i);
        // 이미 뽑힌 숫자와 String concat을 실행한다.
        String perm = picked+s;
        // 뽑고 남은 배열을 저장할 임시 배열을 생성한다.
        List<String> remList = new ArrayList<String>();
        remList.addAll(arr); // 전체를 복사한 다음
        remList.remove(i);   // 뽑은 숫자를 제외한다.
        // concat을 해서 만들어진 숫자가 모든 조합을 가지고 있는 배열에 이미 존재하거나
        // 2이상인지 확인 후 추가한다.
        int iPerm = Integer.parseInt(perm);
        if(!permArr.contains(iPerm) && iPerm > 1) {
             permArr.add(iPerm);
        }
        // 다시 재귀호출한다.
        pick(remList, perm, permArr);
    }
}

최종적으로 permArr에 담겨져 있는 값은 중복이 없고 2 이상인 모든 조합의 배열이 되고 이제 permArr을 순회하면서 소수인지(2부터 자기자신-1 까지 나눠봐서 모든 나머지가 0인지) 검사하는 일만 남게 된다. 

 

따라서 최종 제출 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        List<String> numStr = new ArrayList<>();
        for (int i = 0; i < numbers.length(); i++) {
            char c = numbers.charAt(i);
            numStr.add(String.valueOf(c));
        }
        List<Integer> ansList = new ArrayList<>();
        pick(numStr, "", ansList);
        
        for (Integer i : ansList) {
            boolean isSosu = true;
            for (int j = 2; j < i; j++) {
                 int div = i%j;
                 if(i%j == 0) {
                     isSosu = false;
                 }
            }
            if(isSosu) {
                answer+=1;
            }
        }
        return answer;
    }
    
    public static void pick(List<String> arr, String picked, List<Integer> permArr) {

        for (int i = 0; i < arr.size(); i++) {

            String s = arr.get(i);
            String perm = picked+s;
            List<String> remList = new ArrayList<String>();
            remList.addAll(arr);
            remList.remove(i);
            int iPerm = Integer.parseInt(perm);
            if(!permArr.contains(iPerm) && iPerm > 1) {
                permArr.add(iPerm);
            }

            pick(remList, perm, permArr);
        }
    }
}

 

출처: 프로그래머스 코딩 테스트 연습, 
https://programmers.co.kr/learn/challenges