프로그래머스 - 소수 만들기

문제

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

코딩테스트 연습 - 소수 만들기

 

 

풀이

 

조합을 통해 3개를 뽑아낸 후 합을 구해 소수인지 판단한다.

뽑아낼 수가 3개로 고정되 있어서 3중 for문을 활용해 문제를 해결할 수도 있다.

 

 

코드

 

python

from itertools import combinations 
 
def setPrime():
    l = [False] * 50001
    l[1] = True
    for i in range(2, 50001):
        if l[i] == True: continue
        for j in range(i + i, 50001, i):
            l[j] = True
    return l
 
def solution(nums):
    answer = 0
    primes = setPrime()
    for i in list(combinations(nums, 3)):
        if primes[sum(i)] == False:
            answer += 1
    return answer

 

java

class Solution {
    static int result = 0;
    public int solution(int[] nums) {
        int answer = 0;
        boolean[] primes = getPrime();
        boolean[] checked = new boolean[nums.length];
        combination(nums, checked, 0, nums.length, 3, primes);
        answer = result;
        return answer;
    }
 
    private void combination(int[] nums, boolean[] checked, int index, int n, int r, 
                             boolean[] primes) {
        if (r == 0) {
            int sum = 0;
            for (int i=0; i<nums.length; i++) {
                if (checked[i] == true) {
                    sum += nums[i];
                }
            }
            if (primes[sum] == false)
               result++;
            return;
        }
 
        for (int i=index; i<n; i++) {
            checked[i] = true;
            combination(nums, checked, i + 1, n, r - 1, primes);
            checked[i] = false;
        }
    }
 
    private boolean[] getPrime() {
        boolean[] primes = new boolean[50001];
        primes[1] = true;
        for (int i=2; i<=50000; i++) {
            if (primes[i] == true)
                continue;
            for (int j = i + i; j <= 50000; j += i) {
                primes[j] = true;
            }
        }
        return primes;
    }
}