[프로그래머스] Lv.1 : 소수 만들기 - 자바[Java]

Summer/Winter Coding(~2018)

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

프로그래머스

 

풀이

nums에 있는 숫자들 중 서로 다른 3개를 골라야 하며, 더했을 때 소수가 되는지 판별해야 한다.

서로 다른 3개를 고르는 방법은 DFS를 사용하여 조합을 통해 구한다.

그리고 조합으로 구한 수를 모두 더해서 소수가 되는지 함수를 호출해 판별한다.

 

로직

1. 전역 변수로 조합의 수를 저장하는 comb 배열을 선언하고, 정답을 저장하는 answer를 선언하고 0으로 초기화 한다.

2. 메인 함수(solution 함수)에서 combination(0, 0, nums)를 호출하여 모든 조합의 경우의 수를 구한다.

 

static void combination(int L, int start, int[] nums) : 모든 조합의 경우의 수를 구하고, 조합 수들을 더하여 소수가 된다면 answer를 업데이트

    static void combination(int L, int start, int[] nums) {
        if (L == 3) {
            int cnt = 0;
            for (int i : comb)
                cnt += i;
            
            if (isPrime(cnt)) answer++;
            
            return;
        }
        else {
            for (int i = start; i < nums.length; i++) {
                comb[L] = nums[i];
                combination(L+1, i + 1, nums);
            }
        }
    }

comb 배열에 조합이 되는 숫자를 저장한다.

조합이 완성되면 수를 모두 더하고 isPrime() 함수를 호출해서 소수가 되는지 판별한다.

소수가 된다면 answer에 1을 더한다.

 

static boolean isPrime(int num) : num이 소수라면 true, 소수가 아니면 false 리턴

    static boolean isPrime(int num) {
        if (num == 2) return true;
        
        if (num % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }

 

 

코드

import java.util.*;

class Solution {
    
    static int[] comb = new int[3];
    static int answer = 0;
    
    // 소수인지 판별
    static boolean isPrime(int num) {
        if (num == 2) return true;
        
        if (num % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    // 모든 조합의 경우의 수를 구함
    static void combination(int L, int start, int[] nums) {
        if (L == 3) {
            int cnt = 0;
            for (int i : comb)
                cnt += i;
            
            if (isPrime(cnt)) answer++;
            
            return;
        }
        else {
            for (int i = start; i < nums.length; i++) {
                comb[L] = nums[i];
                combination(L+1, i + 1, nums);
            }
        }
    }
    
    public int solution(int[] nums) {

        combination(0, 0, nums);

        return answer;
    }
}

 

---

다른 풀이 2

nums에 있는 숫자들 중 서로 다른 3개를 고르는 과정을 조합이 아닌 삼중 for문을 사용한다.

nums에 들어있는 숫자의 개수는 3개 이상 50개 이하이므로 크지 않기 때문에, 삼중 for문을 사용하는 것이 실행 시간 측면에서 더 좋은 성능을 보인다.

import java.util.*;

class Solution {
    
    // 소수인지 판별
    static boolean isPrime(int num) {
        if (num == 2) return true;
        
        if (num % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
    
    public int solution(int[] nums) {

        int answer = 0;
        
        int len = nums.length;
        for (int i = 0; i < len-2; i++) {
            for (int j = i+1; j < len-1; j++) {
                for (int k = j+1; k < len; k++) {
                    if (isPrime(nums[i] + nums[j] + nums[k]))
                        answer++;
                }
            }
        }

        return answer;
    }
}