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

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

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

[문제 설명]

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

 

numbers	return
17	3
011	2

 

[풀이]

연산 횟수가 적고 경우의 수는 많은 문제이다. 완전 탐색을 사용해서 문제를 풀었다.

 

소수를 판별하기 앞서 숫자들의 순열을 구해줘야 하는데, 주어진 숫자들로 1개부터 주어진 숫자들의 개수까지 순열을 구해야 한다. 

 

각 자리수에 맞는 순열을 구해준 다음, 그 수들이 소수인지 판별한다.

 

주석을 코드에 달아 놓았기 때문에 코드를 보면 이해할 수 있을 것 같다.

 

[코드]

    ArrayList<Integer> result;
    boolean[] visited;
    
    public int solution(String numbers) {
        result = new ArrayList<Integer>();                //답의 개수를 찾기 위한 arrayList
        visited = new boolean[numbers.length()];
        int[] nums = new int[numbers.length()];
        
        for(int i = 0; i < nums.length; i++) {
            nums[i] = Integer.parseInt(numbers.charAt(i)+"");    //String 형의 숫자들을 int형 배열로 변환
        }
        
        //자리 수 마다 해당 배열을 perm 메서드에 보낸다.
        for(int i = 1; i <= numbers.length(); i++) {    //1개 부터 numbers의 길이까지 숫자의 순열을 구한다.
            int[] resultArr = new int[i];
            perm(nums, resultArr, nums.length, i, 0);
        }
        
        return result.size();
        
    }
    public boolean isPrime(int num) {                    //소수인지 판별하는 메서드
        if(num <= 1) {
            return false;
        }
        if(num == 2 || num == 3) {
            return true;
        }
        
        int end = (int) Math.sqrt(num);
        for(int i = 2; i <= end; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    //n개중 r개를 뽑는다.
    public void perm(int[] nums, int[] resultArr, int n, int r, int index) {
        if(index == r) {
            //0이먼저오는지, 소수인지, 이미 result에 있는지 확인
            
            String realNum = "";
            for(int i = 0; i < resultArr.length; i++) {
                realNum += resultArr[i];
            }
            
            int num = Integer.parseInt(realNum);
            if(isPrime(num)) {
                if(!result.contains(num)) {
                    result.add(num);
                }
            }
            return;
        }
        
        for(int i = 0; i < nums.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                resultArr[index] = nums[i];
                perm(nums, resultArr, n, r, index+1);
                resultArr[index] = 0;
                visited[i] = false;
            }
        }
    }

테스트 케이스 통과

 

느낀 점: 예전에는 못 풀었던 문제인데, 지금은 문제 푸는 방식을 떠올리는 것과 구현하는 데에 크게 어려움을 느끼지 못했다. 조금은 보람차다..