[프로그래머스] 레벨2 소수찾기

https://programmers.co.kr/learn/courses/30/lessons/42839?language=java 

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

 

문제로도 자주 출제되기도 하고, 아직 빠르고 정확하게 코드로 구현을 못하는 걸 보니 경우의 수, 순열과 조합에 대해서 다시 한 번 빡세게 공부해야 될 것 같다. 

 

1. 입력받은 numbers를 이용해서 전체 숫자 경우의 수를 구한다.

   1-1. 이 때, HashSet 자료구조를 이용해서 자동으로 중복을 제거했다.

2. Set을 배열 형태로 변환한 후, 하나씩 꺼내서 소수인지 판별한다.

   2-1. 1은 소수가 아니기 때문에 제외한다.

   2-2. 소수인지 체크해야하는 값이 n이라고 가정하면, 반복문은 sqrt(n) 까지 돌려도 된다. Math.sqrt를 쓰면 double 형태로 변환되서 인덱스 제곱을 이용했다.

   2-3. 만약 중간에 나누어떨어진다면 바로 소수가 아니라고 체크를 한 후 break를 걸어서 그 수에 대한 체크를 끝낸다.

 

그리고 소수를 구하는 부분은 에라스토테네스의 체를 이용해야되나 고민하다가 약간 무지성으로 일단 돌려봤는데 정답이었다. 궁금해서 에라스토테네스의 체를 구현해서 소수를 찾아보았다. 엥? 근데 드라마틱한 차이가 안났다.

 

---

문제 및 입출력

 

 

---

코드1 - 소수찾기 Brute Force

import java.util.HashSet;

class Solution
{
    // 순열 중 중복제거
    static HashSet<String> set = new HashSet<String>();
 
    // 중복을 비허용하는 순열 구하기
    public static void makeNum(String number, String result, boolean[] visit, int depth, int n, int r)
    {
        String add = "";
        
        if(depth==r)
        {
            return;
        }
        
        for(int i=0; i<number.length(); i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                add = result + number.charAt(i);
                
                if(add.charAt(0)!='0')
                {
                    set.add(add);
                }
                
                makeNum(number, add, visit, depth+1, n, r);
                visit[i] = false;
            }
        }
    }
    
    public int solution(String numbers)
    {
        int answer = 0; // 결과
        
        // 순열에 사용하는 변수 설정
        boolean[] visit = new boolean[numbers.length()]; 
        int n = numbers.length();
        
        // 순열 구한 후, set을 array 형태로 변환
        makeNum(numbers, "", visit, 0, n, n);
        Object[] arr = set.toArray();
        
        // 순열 중 숫자골라서 소수구하기        
        for(int i=0; i<arr.length; i++)
        {
            int chk = Integer.valueOf((String)arr[i]);
            
            // 1은 소수에서 제외
            if(chk==1)
            {
                continue;
            }
            
            boolean isPrime = true;
            
            // 나눠떨어질 경우 바로 break
            for(int j=2; j*j<=chk; j++)
            {
                if(chk%j==0)
                {
                    isPrime = false;
                    break;
                }
            }
            
            // 결과값 카운트
            if(isPrime)
            {
                answer++;
            }
        }
        
        return answer;
    }
}

 

결과1

 

---

코드2 - 소수찾기 에라스토테네스의 체

import java.util.Arrays;
import java.util.HashSet;

class Solution
{
    // 순열 중 중복제거
    static HashSet<String> set = new HashSet<String>();
 
    // 중복을 비허용하는 순열 구하기
    public static void makeNum(String number, String result, boolean[] visit, int depth, int n, int r)
    {
        String add = "";
        
        if(depth==r)
        {
            return;
        }
        
        for(int i=0; i<number.length(); i++)
        {
            if(!visit[i])
            {
                visit[i] = true;
                add = result + number.charAt(i);
                
                if(add.charAt(0)!='0')
                {
                    set.add(add);
                }
                
                makeNum(number, add, visit, depth+1, n, r);
                visit[i] = false;
            }
        }
    }
        
    // 에라스토테네스의 체 구현
    public boolean[] makeChe(int n, boolean[] che)
    {
        for(int i=2; i*i<che.length; i++)
        {
            if(!che[i])
            {
                for(int j=i*i; j<che.length; j+=i)
                {
                    che[j] = true;
                }
            }
        }
        
        return che;
    }
    
    public int solution(String numbers)
    {
        int answer = 0; // 결과
        
        // 순열에 사용하는 변수 설정
        boolean[] visit = new boolean[numbers.length()]; 
        int n = numbers.length();
        
        // 순열 구한 후, set을 array 형태로 변환
        makeNum(numbers, "", visit, 0, n, n);
        Object[] arr = set.toArray();
        
        // 에라스토테네스의 체 설정을 위한 초기값 할당
        Arrays.sort(arr);
        int len = arr.length;
        
        // 에라스토테네스의 체 배열 초기값 할당
        boolean[] che = new boolean[Integer.valueOf((String)arr[len-1])+1];
        che[0] = true;
        che[1] = true;
        
        // 에라스토테네스의 체 값 가져오기
        che = makeChe(che.length-1, che);
       
        
        // 에라스토테네스의 체 배열을 활용한 소수여부 판별
        for(int i=0; i<len; i++)
        {
            int chk = Integer.valueOf((String)arr[i]);
            
            if(!che[chk])
            {
                answer++;
            }
        }
        
        return answer;
    }
}

 

결과2