Menu

Subscribe

[JAVA/프로그래머스] Summer/Winter Coding(~2018): 소수 만들기

HEESOO on Programmers

👀 문제

https://programmers.co.kr/learn/courses/30/lessons/12977

👊 도전

1. 설계

  1. 에라토스테네스의 체로 소수를 미리 계산한다.
  2. 조합을 이용하여 3개를 선택한다.
  3. 선택한 숫자들의 합이 소수인지 확인한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
    boolean[] prime, visit;
    int n;
    int answer;
    public int solution(int[] nums) {
        answer = 0;
        n=nums.length;
        Arrays.sort(nums);
        int max=nums[nums.length-1]; // nums에서 제일 큰 값
        prime=new boolean[max*3]; // 3개의 합이 max*3보다는 작음
        visit=new boolean[n];
        
        // 에라토스테네스의 체
        Arrays.fill(prime, true);        
        int range=(int)Math.sqrt(prime.length);
        for(int i=2;i<=range;i++){
            if(!prime[i]) continue;
            for(int j=i+i;j<prime.length;j+=i){
                if(!prime[j]) continue;
                prime[j]=false;
            }
        }
        
        // 조합으로 3개 선택
        comb(0, 0, 0, nums);
        
        return answer;
    }
    
    public void comb(int start, int cnt, int sum, int[] nums){
        if(cnt==3){ // 3개 선택 완료
            if(prime[sum]) { // 소수 체크
                answer++;
            }
            return;
        }
        
        for(int i=start;i<n;i++){ // 조합
            if(visit[i]) continue;
            visit[i]=true; // i를 선택하는 경우
            comb(i+1, cnt+1, sum+nums[i], nums); // i값을 sum에 더해서 재귀 호출
            visit[i]=false; // i를 선택하지 않는 경우
        }
    }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 소수를 미리 구해놓는다
    • 에라토스테네스의 체를 이용한다.
    • 이때 어디까지 찾아 놓을지가 문제인데, nums의 최댓값*3보다는 무조건 작다.
    • 따라서 nums를 오름차순 정렬하고 마지막 값을 max에 저장한 후 max*3까지의 소수를 구한다.
  2. 서로 다른 3개를 선택한다
    • 조합을 이용한다.
    • 중복 선택할 수 없으므로 visit[]를 두고 체크한다.
    • comb()의 파라미터 start는 for문에서 체크할 시작 인덱스(앞까지는 모두 확인했으므로 0부터 또 확인할 필요 없다)
    • cnt: 선택한 숫자 개수
    • sum: 선택한 숫자들의 합
    • cnt==3이면 3개를 모두 선택한 것이므로 미리 구해둔 소수 배열 prime[]을 통해 sum이 소수인지 아닌지 체크한다.
    • 소수가 맞다면 answer++
    • 여기서 중요한 것은 {1,2,7}을 선택해서 10이 되는 것과 {2,3,5}로 10이 되는 것을 모두 카운트 해야 한다는 것이다.

👏 해결 완료!