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

문제

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

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

풀이

백트래킹으로 해결할 수 있었다.

매개변수로 들어온 문자열 numbers를 nums라는 char형 배열로 만들어 주었고 nums를 통해 순열을 돌려주었다. 이때 순열 nPr에서 n은 문자열의 길이가 될 것이고, r은 1부터 ~ 문자열의 길이까지의 모든 순열을 찾아내야 정답을 구할 수 있다.

이후 각 r에 대하여 순열을 구해주고 isPrimeNumber 함수를 통해 해당 순열이 소수인지 아닌지 판별해주었고 소수이면 answer를 1씩 증가시켜주면 문제를 해결할 수 있다.

문제를 풀면서 주의할 점은 순열을 돌리다가 소수인 같은 숫자가 여러 번 나왔으면 중복으로 갯수를 세면 안되는 점을 잘 생각해야한다. 필자는 primeTable이라는 배열을 만들어주어 해당 순열이 이미 소수 판별이 됐는지 확인하여 소수로 이미 판별됐다면 해당 순열을 0으로 만들어주어 중복 처리를 해결할 수 있었다.

또한 이 문제는 다중 for문으로 모든 숫자 순열을 만들어서 해결할 수도 있지만 시간 초과날 가능성을 염두하여 백트래킹으로 푸는 것이 좋을 거 같다. 이외에도 numbers의 길이가 최대 7까지 나올 수 있으므로 소수 판별 함수를 작성할 때 시간 복잡도를 고려하여 함수를 작성해야하는 점을 주의해야한다.

 

 

코드

import java.util.Arrays;

class Solution {

    char[] arr = new char[11];
    boolean[] isUsed = new boolean[11];
    int answer = 0;
    char[] nums;

    boolean[] primeTable = new boolean[10000000];

    public int solution(String numbers) {

        nums = numbers.toCharArray();

        for(int i = 0; i < numbers.length(); i++) {
            permutation(0, i + 1, nums);
        }

        return answer;
    }

    boolean isPrimeNumber(int n) {
        if(n == 0)
            return false;
        if(n == 1)
            return false;

        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0)
                return false;
        }
        return true;
    }

    void permutation(int k, int m, char[] nums) {
        if(m == k) {
            String str = "";
            for(int i = 0; i < m; i++) {
                str += arr[i];
            }
            int num = Integer.parseInt(str);
            if(primeTable[num] == true) {
                num = 0;
            }
            if(isPrimeNumber(num)) {
                primeTable[num] = true;
                answer++;
            }
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!isUsed[i]) {
                isUsed[i] = true;
                arr[k] = nums[i];
                permutation(k + 1, m, nums);
                isUsed[i] = false;
            }
        }
    }
}