[프로그래머스]소수 만들기 - 재귀함수

https://programmers.co.kr/learn/courses/30/lessons/12977

프로그래머스

문제

• nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록  solution 함수를 완성해주세요.

제한사항

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

입출력의 예

   nums      result

  [1,2,3,4]        1

  [1,2,7,6,4]      4

 

입출력의 예 설명

입출력 예#2

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

[1,4,6]을 이용해서 11을 만들 수 있습니다.

[2,4,7]을 이용해서 13을 만들 수 있습니다.

[4,6,7]을 이용해서 17을 만들 수 있습니다.

 

풀이

 

boolean[] visited = new boolean[nums.length]를 하면 nums의 길이 만큼 배열이 생성되고, boolean은 false로 기본값이 들어간다.

combination의 함수(재귀함수)를 이용해서 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 구한다.

※ 매개변수 설명

nums는 서로 다른 수가 들어있다.

visited는 3개의 숫자를 고르기 위해서 true, false를 지정한다. true는 3 개까지만 하기 위해서 n 변수를 3으로 설정

start는 시작 값을 정해주기 위해서 선언 해주었다.

	       boolean[] visited = new boolean[nums.length];
	        
	      result1 += combination(nums, visited, start, n);

 

n은 숫자 3개가 true 일 때 0이 된다. 

그럼 숫자 3개를 다 골랐다는 의미로 num += nums[i]를 통해 숫자 3개의 합을 구하고,

for 문을 통해 소수인지 아닌지 판별 한다.

소수이면 check 값에 true이기에 result 값이 1 증가한다.

if (n == 0) {
    int temp = 0, num = 0;
    boolean check = true;
    for (int i = 0; i < nums.length; i++) {
        if(visited[i] == true) {
           num += nums[i];
        }
    }
			   
    for (int l = 2; l < num; l++) {
        if (num % l == 0) {
            check = false;
            break;
        }
    }
			   
    if (check) result++;
						   
    return result;	 
    
}

 

재귀함수를 통해 각 배열에 true 값을 주는 조건으로 combination(nums, visited, j + 1, n - 1); n이 0일 때 까지 

재귀 함수를 호출하고 n = 0 일 때, 3 개의 수들을 합쳐서 소수인지 아닌지 판별한다.

 

else {
  for(int j = start; j < nums.length; j++) {
      visited[j] = true;
      result += combination(nums, visited, j + 1, n - 1);
      visited[j] = false;
   }
}

 

전체 코드

※재귀 함수의 값을 차곡차곡 쌓이게 하였다.

class Solution {
    public int solution(int[] nums) {
        
       int n = 3, start = 0, result1 = 0;
       boolean[] visited = new boolean[nums.length];    
       result1 += combination(nums, visited, start, n);
	       	   
       return result1;
    }
    
    public static int combination(int[] nums, boolean[] visited, int start, int n) {
		 
       int result = 0;
				   
       if (n == 0) {
          int temp = 0, num = 0;
          boolean check = true;
          for (int i = 0; i < nums.length; i++) {
              if(visited[i] == true) {
                  num += nums[i];
              }
          }
			   
           for (int l = 2; l < num; l++) {
              if (num % l == 0) {
                 check = false;
                 break;
               }
            }
			   
            if (check) result++;
						   
            return result;	 
        } else {
             for (int j = start; j < nums.length; j++) {
                visited[j] = true;
                result += combination(nums, visited, j + 1 , n - 1);
                visited[j] = false;
             }
         }
		   
       return result;
     }
}