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

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

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

우선 숫자를 잘라서 모든 경우의 수로 순열을 만들어야 한다.

또한 순열을 사용할 때 뽑을 숫자의 갯수를 하나씩 증가시켜 주어야한다.

순열을 어캐 구현해야할지 막막해서 블로그를 많이 참고했다.

 

또한 01, 1은 모두 같은 경우기 때문에 맨 앞 자리가 0인 경우는 제외하고 풀어주어야한다.

 

나는 뽑는 갯수에 따라 answerList에 모두 넣고, 작업이 끝난 이후

중복제거 -> 소수 판별

이 순서로 해줌. 

 

근데 다른 사람들 코드를 살펴보니 answerList에 넣기전에 중복제거 & 소수 판별하는 경우도 있더라. 

 

순열이나 조합을 짜는걸 공부를 해야할듯.

import java.util.*;


public class Permutation {
    static LinkedList<String>strList = new LinkedList<>();
    static LinkedList<String> resultList = new LinkedList<>();
    static LinkedList<String> answerList = new LinkedList<>();

    public static void permutation( LinkedList<String> arr,  LinkedList<String> result, int n, int r) {

        if(r == 0) {
            String tempAns = "";
            //01, 1 은 모두 1로 간주하기 때문에 앞자리가 1은 제외 시켜야함 
            if(!result.get(0).equals("0")) {
                for(int i = 0; i < result.size(); i++) {            
                    tempAns = tempAns + result.get(i);
                }
                answerList.push(tempAns);
            }
           return;
        } 
        for(int i = 0 ; i < n; i++) {
            result.add(arr.remove(i).toString());
            permutation(arr, result, n-1, r-1);
            arr.add(i, result.remove(result.size() -1));
        }
    }
    public static int solution(String numbers) {
        int answer = 0;
        //strList에 numbers를 넣어줌
        for(int i = 0; i < numbers.length(); i++) {
            strList.add(Character.toString(numbers.charAt(i)));
        }

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

        //중복 제거를 위해 List -> Set -> List로 변환함 
        HashSet <String> set =  new HashSet<>(answerList);
        ArrayList <String> realanswer = new ArrayList<String>(set);
   
        for(int i = 0; i< realanswer.size(); i++) {
            boolean isPrime = false;
            int num = Integer.parseInt(realanswer.get(i));
            int sqrt = (int) Math.sqrt(num);
            if(num == 1) {
                isPrime = false;
            }
            else if(num == 2) isPrime = true;
            else {
                isPrime = true;
                for(int j = 2; j <= sqrt; j++) {
                    if(num % j == 0) {
                        isPrime = false;
                        break;
                    }
                }
            }
            if(isPrime) answer++;
        }
        return answer;
    }
 
    public static void main(String [] args){

        int tet = solution("011");
        System.out.println(tet);
    }
}