프로그래머스 (Level 1) - 소수 만들기

문제 설명

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

 

풀이

주어진 정수형 배열 nums에서 임의의 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하는 문제이다.

 

우선, 정수형 배열 nums에서 완전 탐색 기법을 사용해서 3개의 숫자로 구성할 수 있는 모든 조합을 탐색하였다. 3개의 숫자 조합을 탐색할 때마다 3개 숫자의 합을 구하고, 구한 숫자가 소수인지 아닌지 판별 함으로써 문제를 해결하였다.

 

전체 소스코드

import java.io.*;
import java.util.*;

public class Solution05 {
	static int[] numbers;
	static boolean[] visited;
	static int[] arr = new int[3];

	static int answer = 0;

	public int solution(int[] nums) {
		numbers = nums;
		visited = new boolean[nums.length];

		dfs(0, 0);

		return answer;
	}

	/** 3개의 숫자로 구성할 수 있는 모든 조합을 탐색 */
	static void dfs(int start, int depth) {
		if (depth == 3) {
			int target = 0;

			for (int number : arr)
				target += number;

			if (isTrue(target))
				answer++;

			return;
		}

		for (int i = start; i < numbers.length; i++) {
			if (visited[i] == false) {
				visited[i] = true;

				arr[depth] = numbers[i];
				dfs(i, depth + 1);

				visited[i] = false;
			}
		}
	}

	/** 소수를 판별하는 메서드 */
	static boolean isTrue(int target) {

		for (int i = 2; i <= target / 2; i++) {
			if (target % i == 0)
				return false;
		}

		return true;
	}
}