[프로그래머스] 소수 찾기 (Java)

 

프로그래머스

전체 조합 만들기 + 소수 구하기의 두 가지를 수행하면 해결할 수 있는 문제이다.

 

- 문자열 쪼개서 배열로 저장하기 : String[] arr

- arr 각 요소의 방문 여부를 체크해줄 int 배열 선언 : int[] visited

- 전체 조합 숫자를 넣어줄 set 선언: HashSet<Integer> set

- 재귀 함수를 사용하여 완전 탐색을 통해 전체 문자열의 조합 구하기 : private void addNum

  1) 현재 문자열 삽입 (빈문자열 제외)

  2) arr 배열을 탐색하며

    2-1) visited 배열에서 방문체크가 되지 않은 문자열인 경우에만 로직 수행

    2-2) visited 배열을 복사한 clone 배열에 방문여부 1로 표시 (visited에 그냥 표시하면 루프 한 번에 모든 요소가 1로 표기되므로 복제가 필요했음)

    2-3) clone 배열, str + arr[i](이전문자열 + 현재 문자열)를 파라미터로 하여 addNum 호출

- addNum 종료 후 소수 여부 체크하여 answer 증가 (소수 체크 로직은 생략)

 

Note

- 일단은 이게 최선이었는데 처음에 전체 조합을 만드는 방법이 바로 떠오르지 않아 시간이 걸렸다. 더 깔끔할 수도 있었을 것 같은데 조합과 순열을 손에 익혀야겠다.

import java.util.*;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        
        String[] arr = numbers.split("");
        int[] visited = new int[arr.length];
        
        HashSet<Integer> set = new HashSet<>();
        
        addNum(arr, set, visited, "");
        
        for(int n : set){
            if(n == 0 || n == 1){
                continue;
            }
            Boolean isPrime = true;
            for(int i = 2; i*i <= n; i++){
                if(n % i == 0){
                    isPrime = false;
                    break;
                }
            }
            answer += isPrime ? 1 : 0;
        }
        
        return answer;
    }
    
    private void addNum(String[] arr, HashSet<Integer> set, int[] visited, String str){
        if(!str.equals("")){
            set.add(Integer.parseInt(str));
        }
        
        for(int i = 0; i < arr.length; i++){
            if(visited[i] == 0){                
                int[] clone = visited.clone();
                clone[i] = 1;
                addNum(arr, set, clone, str + arr[i]);
            }
        }
    }
}