[Java/프로그래머스/브루트 포스] 소수 찾기 (Level 2)

문제

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

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

 

코드

• checkPrime 함수 

2부터 √n 까지 나누면서 체크한다. (√n 을 기준으로 나눠지는 수가 대칭되기 때문이다. 이해가 안된다면 아래 링크 참고)

https://programmers.co.kr/questions/11572

소수가 맞아도 ans라는 전역 ArrayList<Integer>에 같은 값이 있는지 확인한다. 중복을 피하기 위함이다.

 

• permutation 함수

range는 검사할 배열의 원소 수+1로 보면 된다.

- range가 1일 때, 순열을 완성했으므로 (위 그림 중 가장 오른쪽 상태) 소수 검사를 진행한다. (call checkPrime)

- range>1일 때, 위 그림처럼 진행한다.

   - (그림의 가운데 배열)start의 위치와 start+i를 바꾼다(swap). → (그림의 가장 오른쪽 배열 상태)start+1의 위치로 재귀함수 호출

   - permutation이 완료되고 return되면 다음 순열을 위해 상태를 원래 상태로 swap한다.

 

• solution 함수

예를 들어 "17"의 경우, 7, 17, 71 세가지 경우가 소수에 해당한다.

numbers 문자열에서 어떤 문자를 선택하는지를 구현해야 한다. (숫자 한개 ~ 숫자 전체)

이를 이진수로 구현했다.

- int max_idx : 문자열 길이 만큼의 크기를 가진 배열이 있을 때, 이진수로 들어갈 수 있는 최댓값+1이다.

- int[] flags : 문자열 길이 만큼의 크기를 가진 배열

예를 들어, 문자열의 길이가 2라면 0부터 3까지 들어갈 수 있다.(00, 01, 10, 11)

이 경우 flags는 2칸의 int형 배열이고, max_idx는 4이다.

 

- for문 : 0부터 3까지 반복한다.

- int arrN : permutation 함수에 참여할 배열의 길이

- int[] nums : permutation 함수에 참여하는 배열

flags를 0과 1로 채운다. 이 경우 값이 1인 곳의 인덱스가 permutation에 참여할 문자의 인덱스다.

예를 들어, flags={0, 1}인 경우 numbers의 "7"이 참여한다. nums={7}이다.

flags={1,1}인 경우 numbers의 "17"이 참여한다. nums={1, 7}이다.

import java.util.ArrayList;

class Solution {
    static ArrayList<Integer> ans = new ArrayList<>();
    static void checkPrime(int n){
    	if(n<2)
    		return;
        boolean prime = true;
        
        for(int i=2; i<=Math.sqrt(n); i++){
            if(n%i==0){
                prime=false;
                break;
            }
        }
        if(prime&& !ans.contains(n)){
            //System.out.println(n);
            ans.add(n);
        }
    }
    
    static void swap(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    
    static void permutation (int[] nums, int start, int end){
        int range = end - start;
        
        if(range == 1){
            String n = "";
            for(int num : nums){
                n+=num;
            }
            checkPrime(Integer.parseInt(n));
        }else{
            for(int i=0; i<range; i++){
                swap(nums, start, start+i);
                permutation(nums, start+1, end);
                swap(nums, start, start+i);
            }
        }
    }
    public static int solution(String numbers){
        int answer = 0;
        int length = numbers.length();
        
        int[] flags=new int[length];
        int idx_max =(int)Math.pow(2,length);
        for(int i=1; i<idx_max; i++){
            int arrN = 0;
            int tmp = i;
            for(int j=length-1; j>=0;j--){
            	flags[j] = tmp%2;
                if(flags[j]!=0)
                    arrN++;
                tmp/=2;
            }

            int[] nums = new int[arrN];
            int idx=0;
            for(int j=0; j<length; j++){
                if(flags[j]!=0){
                    nums[idx]=Integer.parseInt(numbers.substring(j,j+1));
                    idx++;
                }
            }
            permutation(nums, 0, arrN);
        }
        answer = ans.size();
        return answer;
    }
}