[PGM_42839] 소수 찾기

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42839

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 완전탐색, 순열

1. 문제 이해

String으로 숫자에 대한 문자열이 입력으로 주어지고, 그 문자열에 있는 숫자들을 한 글자씩 취급하여 새로운 조합의 숫자를 만들었을 때 소수인 경우를 구하는 문제이다. 

 

2. 접근방법

문제를 해결하기 위해 주어지는 숫자를 순열로 나타낼 수 있는 경우의 수를 모두 만들어주었다. 그리고 해당 숫자들을 사용할지 안할지를 재귀로 판단하여 모든 경우를 세어줄 수 있도록 해주었고, 중복되는 경우를 제거하기 위하여 집합을 사용해주었다.

 

3. 세부 해결방안

private boolean nextPermutation(int[] numbers){
    int prevIndex;
    int n = numbers.length;
    int nextIndex = n-1;
    int changeIndex = -1;

    for(int i = n-2; i >= 0; i--){
        prevIndex = nextIndex;
        nextIndex = i;

        if(numbers[nextIndex] < numbers[prevIndex]){
            changeIndex = nextIndex;
            break;
        }
    }

    if(changeIndex == -1)
        return false;

    for(int i = n-1; i > changeIndex; i--){
        if(numbers[i] > numbers[changeIndex]){
            swap(numbers, i, changeIndex);
            break;
        }
    }
    while(++changeIndex < --n){
        swap(numbers,changeIndex,n);
    }
    return true;
}

순열의 다음 위치를 찾아주는 메소드를 만들어 해결하였다. 위 메소드로 문자로 주어진 숫자들의 순열을 구해주었다.

public int recursiveCheckNumber(int[] numbers, boolean[] checked, int checkedNumber,Set<Integer> set) {
    if(checkedNumber == numbers.length){
        String number = "";
        for(int i = 0; i < numbers.length; i++){
            if(checked[i])
                number = number + numbers[i];
        }

        if(number.equals(""))
            return 0;

        if(set.contains(Integer.parseInt(number)))
            return 0;
        set.add(Integer.parseInt(number));

        if(isPrime(Integer.parseInt(number)))
            return 1;
        else
            return 0;
    }

    checked[checkedNumber] = true;
    int a = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
    checked[checkedNumber] = false;
    int b = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
    return a + b;
}

구해진 순열에 대해서도 일부를 사용하지 않는 경우에 대한 처리도 해주어야하기 때문에 재귀로 돌아가며 사용할지 안할지를 체크하였다. 이 때 집합을 사용하여 중복하여 체크하는 경우를 제거하여주었다.

 

public boolean isPrime(int number){
    if(number == 1 || number == 0)
        return false;
    for(int i = 2; i*i <= number; i++){
        if(number % i == 0)
            return false;
    }
    return true;
}

소수를 구하는 방법은 $O(√n)$의 방법을 사용해주었다. 소수는 $√n$까지만 확인해주면 되기 때문에 위 처럼 구현하여 n번 반복이 아닌 √n까지만 확인할 수 있도록 하였다.

구현코드

package pgm_42839;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int solution(String numbers) {
        int[] permutation = new int[numbers.length()];
        for(int i = 0; i < permutation.length; i++)
            permutation[i] = i;

        int count = 0;
        Set<Integer> set = new HashSet<>();
        do{
            int[] inputNumbers = new int[numbers.length()];
            for(int i = 0; i < permutation.length; i++){
                inputNumbers[i] = numbers.charAt(permutation[i]) - '0';
            }
            boolean[] checked = new boolean[numbers.length()];
            count += recursiveCheckNumber(inputNumbers,checked,0,set);
        }while (nextPermutation(permutation));

        return count;
    }

    private boolean nextPermutation(int[] numbers){
        int prevIndex;
        int n = numbers.length;
        int nextIndex = n-1;
        int changeIndex = -1;

        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;

            if(numbers[nextIndex] < numbers[prevIndex]){
                changeIndex = nextIndex;
                break;
            }
        }

        if(changeIndex == -1)
            return false;

        for(int i = n-1; i > changeIndex; i--){
            if(numbers[i] > numbers[changeIndex]){
                swap(numbers, i, changeIndex);
                break;
            }
        }
        while(++changeIndex < --n){
            swap(numbers,changeIndex,n);
        }
        return true;
    }

    private void swap(int[] numbers, int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }

    public int recursiveCheckNumber(int[] numbers, boolean[] checked, int checkedNumber,Set<Integer> set) {
        if(checkedNumber == numbers.length){
            String number = "";
            for(int i = 0; i < numbers.length; i++){
                if(checked[i])
                    number = number + numbers[i];
            }

            if(number.equals(""))
                return 0;

            if(set.contains(Integer.parseInt(number)))
                return 0;
            set.add(Integer.parseInt(number));

            if(isPrime(Integer.parseInt(number)))
                return 1;
            else
                return 0;
        }

        checked[checkedNumber] = true;
        int a = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
        checked[checkedNumber] = false;
        int b = recursiveCheckNumber(numbers,checked,checkedNumber+1,set);
        return a + b;
    }

    public boolean isPrime(int number){
        if(number == 1 || number == 0)
            return false;
        for(int i = 2; i*i <= number; i++){
            if(number % i == 0)
                return false;
        }
        return true;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)