[프로그래머스/Lv.2] 소수 찾기 - Java

문제

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

프로그래머스

---

리뷰

코딩테스트 고득점 Kit에서 완전탐색으로 분류되어 있는 문제이다. 아래와 같은 방법으로 풀었다.

 

1. 순열(nPr)로 numbers를 구성하는 숫자들로 만들 수 있는 모든 정수를 만든다.

2. 만들어진 각 수들에 대해 소수인지 판단하여 리스트에 저장한다.

3. 소수만을 저장한 리스트의 길이를 구한다.

 

파이썬으로는 itertools.permutations으로 numbers로 만들 수 있는 모든 정수를 쉽게 만들 수 있었기 때문에 간단했다. 이번에 Java로 풀면서 순열을 만드는 방법을 이해하고 직접 구현하느라 시간이 좀 걸렸다.

---

풀이 방법

순열 Permutation 구현 방법

참고: https://bcp0109.tistory.com/14

순열 Permutation (Java)

순열(nPr)은 n개의 요소 중 r개의 요소를 골라 순서대로 나열하는 것이다.

depth 이전까지의 원소들은 자리를 고정하고, depth번째부터 마지막 사이에 있는 원소들 중 두 개씩 골라 자리를 바꿔준다.재귀를 이용하여 구현할 수 있는데, depth와 r값이 일치할 때 하나의 순열을 완성했다고 볼 수 있다.

 

단순히 순열을 출력하면 끝나는 것이 아니라 이를 저장해서 반환해야 하므로, 완성된 순열을 담을 ArrayList를 항상 매개변수로 전달한다.

 

소수 판별 방법

정수 n이 소수인지 아닌지 확인하려고 할 때, n 미만의 수(1~n-1)들로 n을 나눠보고 나머지가 0인 수를 세는 방식을 사용했다. 소수는 1과 n만을 약수로 가진다. 따라서 소수를 n 미만의 수들로 n을 나눠본다면 나머지가 0인 수는 1밖에 나오지 않는다. 다시 말해서, n을 n 미만의 수들로 나눴을 때 나머지가 0인 수가 2개 이상 나온다면 그것은 소수가 아니다.

 

반복문으로 이것을 구현할 수 있는데, 제곱수(11^2=121) 등의 상황에서 오류가 발생하지 않도록 반복문의 초기화와 조건식을 잘 설정해야 한다. 

 

그리고 n 미만의 수를 처음부터 끝까지 나누다 보면 소요 시간이 늘어나서 시간초과가 발생하기도 한다. 적절한 조건에서 결과를 반환하도록 만드는 것이 좋을 것 같다.

---

코드

import java.util.ArrayList;

class Solution {
    public int solution(String numbers) {
        int answer = 0;
        int len = numbers.length();

        char[] numArr = numbers.toCharArray();

        ArrayList<Integer> numPer = new ArrayList<>();  // numbers로 만든 모든 순열 저장하는 리스트
        for(int i=1;i<=len;i++){
            ArrayList<Integer> temp = new ArrayList<>();
            permutation(numArr, len, i, 0, temp);
            numPer.addAll(temp);
        }

        ArrayList<Integer> result = new ArrayList<>(); // 순열 중 소수인 것을 저장할 리스트
        for(int i=0;i<numPer.size();i++){
            int cur = (int)numPer.get(i);
            if (result.contains(cur))   // 중복 체크
                continue;
            else if(isPrime(cur))
                result.add(cur);
            else
                continue;
        }

        answer = result.size();
        return answer;
    }

    // num이 소수인지 판단하는 함수
    private boolean isPrime(int num){
        int count = 0;
        if(num==0 || num==1)
            return false;
        for(int i=1;i<num;i++){
            if(num%i==0)
                count+=1;
            if(count>=2)
                return false;
        }

        return true;
    }

    // arr의 n개의 요소에서 r개를 가지고 만들 수 있는 모든 순열을 resultList에 담아 반환하는 함수
    private void permutation(char[] arr, int n, int r, int depth, ArrayList<Integer> resultList){        
        if (depth == r){
            char[] temp = new char[r];
            System.arraycopy(arr, 0, temp, 0, r);
            String cur = new String(temp);
            resultList.add(Integer.parseInt(cur));
            return;
        }
        else if(depth<r){
            // depth-1까지의 요소는 고정, 다음 요소들 중 두 개를 골라 자리를 바꿈 
            for(int i=depth;i<n;i++){
                swap(arr, depth, i);
                permutation(arr, n, r, depth+1, resultList);
                swap(arr, depth, i);
            }
        }
    }


    private void swap(char[] arr, int i, int j){
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}