[프로그래머스] Lv.1 소수 만들기 (브루트 포스 알고리즘, Java)

 

문제설명

입력 & 출력

나의 풀이

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;

        for(int i = 0 ; i < nums.length -2 ; i++){
            for(int j = i+1 ; j < nums.length - 1; j++){
                for(int k = j + 1 ; k < nums.length; k++){
                    int sum = nums[i] + nums[j] + nums[k];
                    if(isPrime(sum)){
                        //System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
    public static boolean isPrime(int n){
        if(n <= 1) return false;
        if(n == 2) return true;
        
        if(n % 2 == 0) return false;
        
        for(int i = 3; i < n ; i+=2){
            if(n % i == 0) return false;
        }
        
        return true;
    }
}

 

이번 문제는 배열의 요소 중 3개의 요소를 더해서 소수를 만드는 문제입니다.

 

브루트 포스 알고리즘을 사용하면 모든 가능한 조합을 시도하여 최적해를 놓치지 않기 때문에, 문제 해결의 확실성을 보장할 수 있습니다.

 

따라서 브루트 포스 알고리즘을 사용했습니다.

 

먼저 소수를 판별할 수 있는 isPrime()이라는 함수를 만들어줍니다. 해당 함수에서는 소수를 구하는 로직이 있습니다.

소수(prime number)는 1과 자기 자신만을 약수로 가지는 자연수를 말합니다.
즉, 소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 수입니다.

 

그리고 3개의 모든 가능한 조합을 위해 3중 for문을 사용하고, i,j,k 를 더한 합 sum이 소수인지 판별하고 소수라면 카운트를 증가하는 방식입니다.

 

 

 

참고 ❗️

[Algorithm] 완전 탐색, 브루트 포스: 가장 단순한 알고리즘(Brute Force) 알아보기