알고리즘 풀이 - 프로그래머스(소수 만들기(Lv 1), 소수)

 

관련글

 

소수 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

3개 이상 50개 이하로 주어지는 숫자 중 3개를 선택하여 모두 합했을 때, 그 합이 소수가 되는 경우의 수를 구하는 문제

(난이도 1)

 

 

2. 풀이

 

이 문제에서는 2가지를 해결 해야 한다.

① 배열에서 3개의 숫자를 선택하여 합하기
  - 재귀 / 반복문을 통해 해결
② 소수 구하기
  - 소수 구하기 관련 포스팅 참고

 

우선, ①과 관련해서는 배열에서 3개의 숫자를 고르기만 하면 되므로, 재귀를 통해서 3개가 골라질 때까지 진행하거나, 3중 반복문을 통해 3개의 숫자를 고르면 된다.

자세한 방법은 코드를 통해 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① 재귀를 통해서 풀기

class Solution {
    public int solution(int[] nums) {
        // 에라토스테네스의 체 구성
        boolean[] notPrime = new boolean[50001];
        
        // 0과 1은 소수가 아님을 미리 설정
        notPrime[0] = true; notPrime[1] = true;
        
        for(int i=2; i < notPrime.length; i++){
            // 현재 값이 소수인 경우 
            if(!notPrime[i]){
            
                // 배수가 되는 모든 값을 소수가 아니게 처리
                for(int j=i+i; j < notPrime.length; j+=i){
                    notPrime[j] = true;
                }    
            }
        }
        
        int answer = 0;
        answer += pickThree(nums, notPrime, 0, 0, 0);    
        return answer;
    }
    
    private int pickThree(int[] nums, boolean[] notPrime, int used, int sum, int idx){
    
        // 숫자 3개 선택하였고 합이 소수인 경우 1 반환
        if(used == 3 && !notPrime[sum]) return 1;
        
        // 범위를 넘었거나 3개 이상 선택된 경우 0 반환
        if(idx >= nums.length || used >= 3) return 0;
        
        // 중복 숫자가 없도록 현재 전달된 idx에서 시작하여 3개의 숫자를 고를 때까지 반복
        int retVal = 0;
        for(int i=idx; i < nums.length; i++){
            retVal += pickThree(nums, notPrime, used+1, sum+nums[i], i+1);    
        }
        return retVal;
    }
}

 

 

② 3중 반복문 쓰기

class Solution {
    public int solution(int[] nums) {
        // 에라토스테네스의 체 구성
        boolean[] notPrime = new boolean[50001];
        
        // 0과 1은 소수가 아님을 미리 설정
        notPrime[0] = true; notPrime[1] = true;
        
        for(int i=2; i < notPrime.length; i++){
            // 현재 값이 소수인 경우
            if(!notPrime[i]){
                for(int j=i+i; j < notPrime.length; j+=i){
                    notPrime[j] = true;
                }    
            }
        }
        
        // 3중 반복문 통해서 i, j, k의 3개 숫자를 고름
        int answer = 0;
        for(int i=0; i < nums.length-2; i++){  // 2개 남겨놓을 수 있는 부분까지
            for(int j=i+1; j < nums.length-1; j++){  // 1개 남겨놓을 수 있는 부분까지
                for(int k=j+1; k < nums.length; k++){ // 마지막까지
                    if(!notPrime[nums[i] + nums[j] + nums[k]]) answer++;
                }
            }
        }
         
        return answer;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.