[Algorithm] 소수 만들기

'소수 만들기' 정의는 다음과 같다.

 

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

---

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

 

다음과 같이 코드를 작성했다.

import java.util.ArrayList;

class Solution {

	public int solution(int[] nums) {
		int answer = 0;
		int n = nums.length;
		int r = 3;
		int[] checkCombArr = new int[n];

		ArrayList<ArrayList<Integer>> combList = new ArrayList<ArrayList<Integer>>();
		combination(combList, checkCombArr, nums, 0, n, r, 0);

		for (ArrayList<Integer> comb : combList) {
			int sum = 0;
			boolean prime = true;

			// 조합 원소 합 연산
			for (Integer element : comb) {
				sum += element;
			}

			// 소수 확인
			for (int i = 2; i < sum; i++) {
				if (sum % i == 0) {
					prime = false;
					break;
				}
			}

			if (prime) {
				answer++;
			}
		}
		return answer;
	}

	// 조합 생성
	public void combination(ArrayList<ArrayList<Integer>> combList, int[] checkCombArr, int[] arr, int index, int n, int r,
			int target) {
		if (r == 0) {
			ArrayList<Integer> innerComb = null;
			innerComb = new ArrayList<Integer>();

			for (int i = 0; i < index; i++) {
				// System.out.print(arr[checkCombArr[i]]);
				innerComb.add(arr[checkCombArr[i]]);
			}
			combList.add(innerComb);
			// System.out.println("");
		} else if (target == n) {
			return;
		} else {
			checkCombArr[index] = target;
			combination(combList, checkCombArr, arr, index + 1, n, r - 1, target + 1);
			combination(combList, checkCombArr, arr, index, n, r, target + 1);
		}
	}

}

 

1. nC₃ 조합 리스트를 생성한다.

2. 각 조합의 원소 합이 소수인지 판별한다.

 

combination() 매개변수 의미는 다음과 같다.

combList	조합을 뽑아낼 리스트
checkCombArr	조합에 뽑혔는지 체크하는 배열
arr	조합 생성 대상 배열
index	조합에 뽑혔는지 체크를 위한 인덱스
n	조합 생성 대상 배열 사이즈
r	조합 사이즈
target	재귀 호출 중단 조건

 

r == 0일 경우, innerComb에 조합을 add하고 innerComb를 comList에 add한다.

target == n일 때까지 재귀 호출을 이용하여 최종적으로 조합 리스트를 생성한다.

 

소수 판별은 학부 때 자주 봐서 익숙하지만, 재귀호출을 이용한 조합 생성은 집중해서 분석하지 않으면 이해하기 힘들다.

 

combination() 메소드가 조합을 반환하는 것이 아니라, 매개변수 자체 값을 변경시켜 조합을 생성하는 것이 조금 아쉽다.

조합을 만들어 사용하는 문제는 앞으로도 많이 마주칠 듯 하다. 순열 생성도 같이 공부하는 것이 좋겠다.