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

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

문제

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

조건

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

풀이

해당 문제는 조합과 소수 확인법을 이용해서 문제를 해결했다. 먼저 조합을 이용하여 전체 배열에서 3개를 중복이 안되도록 뽑아 더해주고 더한 값이 소수인지를 체크하여 카운트를 증가시켜줬다.

소수를 체크하기 위해 해당 숫자의 제곱근까지 반복문을 돌면서 % 연산을 해주었고, 이 방법은 해당 숫자의 약수들의 중간값까지 체크하는 효율적인 소수 체크 방법이다. 해당 방법을 이용해 문제를 해결할 수 있었다.

코드

class Solution {
	static int answer = 0;
    public static int solution(int[] nums) {
        boolean[] visit = new boolean[nums.length];
        comb(0,0,0,nums,visit); // 조합을 이용해 전체 배열에서 3개 뽑기
        return answer;
    }

	private static void comb(int start,int index, int sum, int[] nums,boolean[] visit) {
		if(index == 3) { // 3개 뽑으면 소수인지 체크
			boolean flag = false;
			for (int i = 2; i <= Math.sqrt(sum); i++) { // 소수 확인법 사용
				if(sum%i == 0) {
					flag = true; 
					break;
				}
			}
			if(!flag) // 나눠진게 없으면 소수임 증가
				answer++;
			return;
		}
		for (int i = start; i < visit.length; i++) {
			if(visit[i])
				continue;
			visit[i] = true;
			comb(i,index+1,sum + nums[i],nums,visit);
			visit[i] = false;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드