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

1. 문제 분석

주어진 숫자를 사용해서 소수를 만드는 것이다.

테스트케이스 1을 먼저 보자. 17로 만들 수 있는 소수는 총 7, 17, 71로 3개가 된다.

여기서 바로 구현하는 방법을 얻을 수 있다. 순서에 상관없이 모든 경우의 수를 뽑자. 순열로 소수를 판별하는 문제다.

 

이번 문제에서는 백트래킹으로 순열을 찾았다. 찾은 수들은 제곱근으로 소수를 찾았다.

순열관련 포스팅은 밑의 글을 참고하자.

2022.09.21 - [문법/Java] - [Java] 순열

[Java] 순열

제곱근으로 소수를 구하는 방법은 생각보다 간단하다.

예를들어 12라는 숫자를 생각하자. 12의 약수는 1, 2, 3, 4, 6, 12가 된다.

이 수를 전부 찾으면 시간이 많이 걸릴 것이다. 그래서 우리는 반만 생각해서 소수인지 판별해보자.

    public boolean getPrime(int num){
        //0과 1은 소수가 아니다
        if(num == 0 || num == 1){
            return false;
        }
        //제곱근을 구하고
        int sqrt = (int)Math.sqrt(num);
        //검사를 한다, 0과 1은 없어도 상관없을 것
        for(int i = 2; i<=sqrt; i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }

먼저 0과 1은 소수가 아니므로 제외를 한다.

12의 제곱근은 3.xxx..가 된다. 그렇다면 for문에서 검사하는 것은 2, 3으로 1, 2, 3, 4, 6, 12가 될 것이다.

이제 숫자를 맨앞과 맨뒤로 보자. (1,12), (2,6), (3,4)가 되는데 꼭 뒤에 숫자도 소수인지 확인을 해야할까?

 

2를 예로 들어보자. 12 / 2 = 6, 12/ 6 = 2가 된다. 즉, 하나만 검사해줘도 된다는 것이다.

이 문제 또한 소수인지 전부 검사하면 시간초과가 날 것이다. 소수 구하는건 기본적으로 알고가자.

2. 구현

import java.io.IOException;
import java.util.ArrayList;


public class Solution {

    ArrayList<Integer>list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String numbers = "123";
        System.out.println(solution.solution(numbers));
    }

    public void powerSet(char[] arr, char[] output, boolean[] visited, int depth){
        //depth의 개수만큼 반복
        if(depth > 0){
            String temp = "";
            for(int i = 0; i<depth; i++){
                temp += output[i];
            }
            int data = Integer.parseInt(temp);
            if(!list.contains(data)) list.add(data);
        }
        for(int i = 0; i< arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                output[depth] = arr[i];
                powerSet(arr,output,visited,depth+1);
                output[depth] = ' ';
                visited[i] = false;
            }
        }
    }

    public boolean getPrime(int num){
        //0과 1은 소수가 아니다
        if(num == 0 || num == 1){
            return false;
        }
        //제곱근을 구하고
        int sqrt = (int)Math.sqrt(num);
        //검사를 한다, 0과 1은 없어도 상관없을 것
        for(int i = 2; i<=sqrt; i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }

    public int solution(String numbers) {
        //재귀로 부분 집합을 구하기 -> char 배열로 받아 백트래킹으로 접근
        int size = numbers.length();
        int result = 0;

        char[] arr = numbers.toCharArray();
        char[] output = new char[size];
        boolean[] visited = new boolean[size];
        powerSet(arr,output,visited,0);
        //나온 숫자가 소수인지 판별 -> 제곱근 사용
        for (Integer integer : list) {
            if (getPrime(integer)) {
                System.out.println(integer);
                result++;
            }
        }
        return result;
    }
}

순열 구하는 부분에서 depth > 0 크다는 것은 1개라도 뽑은 것을 의미한다.

나머지 부분은 어렵지 않게 할 수 있다.

3. 마무리

이 문제.. 재귀라는 것도 모르고 그냥 풀었던 문제다.

친형에게 엄청 도움을 받아서 재귀부터 다시 배웠는데 포스팅이 안된상태라 다시 풀어보았다.

보자마자 아~ 순열로 부분집합 뽑아서 소수인지 봐야지~ 가 나오는걸 보면 알고리즘 실력이 조금은 늘었지 않았나 싶다..