프로그래머스 소수 만들기 JAVA 풀이 (조합, 소수 판별)

🔗 문제 링크

프로그래머스

 

---

📌 문제 개요

정수 배열 nums에서 서로 다른 숫자 3개를 선택한다.

선택한 숫자들의 합이 소수가 되는 경우의 개수를 구하는 문제이다.

 

예를 들어 nums = [1, 2, 3, 4]인 경우, 합이 소수인 경우는 7 하나뿐이므로 결과는 1이다

1 + 2 + 3 = 6
1 + 2 + 4 = 7
1 + 3 + 4 = 8
2 + 3 + 4 = 9

---

📌 접근 방법

숫자 3개를 선택해야 하므로 조합을 생성한다.

 

중복 없이 선택하기 위해 3중 for문을 사용하고,

인덱스를 i < j < k 형태로 유지하여 같은 조합이 여러 번 생성되지 않도록 한다.

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];
        }
    }
}

 

각 조합의 합을 구한 뒤 소수인지 판별하여 개수를 카운트한다.

---

📌 핵심 아이디어

1. 조합 생성

인덱스를 순차적으로 증가시키면 중복 없이 모든 조합을 만들 수 있다.

i < j < k

ex)

[1, 2, 3, 4]

 

(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)

---

2. 소수 판별

소수는 1과 자기 자신만을 약수로 가지는 수이다.

2부터 제곱근까지 나누어 떨어지는 수가 있는지만 확인하면 된다.

public boolean isPrime(int num) {
    if (num < 2) return false;

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

    return true;
}

예를 들어 36의 약수는 다음과 같이 쌍으로 존재한다.

1 × 36
2 × 18
3 × 12
4 × 9
6 × 6

제곱근인 6까지만 확인해도 약수 존재 여부를 알 수 있기 때문에 불필요한 연산을 줄일 수 있다.

---

📌 전체 코드

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)) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }

    public boolean isPrime(int num) {
        if (num < 2) return false;

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

        return true;
    }
}

 

---

📄 정리

이 문제는 크게 두 가지 개념으로 해결할 수 있다.

• 조합 생성
• 소수 판별

3중 for문을 통해 중복 없이 숫자 3개를 선택하고,

선택한 숫자의 합을 제곱근까지 검사하는 방식으로 소수 여부를 판단하면 된다.