소수 만들기_Java

Summer/Winter Coding(~2018)

🔥 소수 만들기 🔥

---

👀 문제

주어진 숫자 중 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

---

🙋‍♀️ 풀이

import java.util.*;

class Solution {
	1️⃣
    static int  answer = 0;
    
    2️⃣
    public int solution(int[] nums) {
        int r=3; 
       
        combination(nums, new boolean[nums.length], 0, 0, r);
       
        return answer;
    }
    
    3️⃣
    public static void combination(int[] arr , boolean[] visited, int start, int depth, int r){
        
        List<Integer> sum = new ArrayList<>();
        int s = 0;
        int n = 0;
        
        4️⃣
        if(depth == r){ 
            for(int i=0;i<arr.length;i++){ 
                if(visited[i]) {
                    s += arr[i];                    
                }
            }
            sum.add(s);
            
            5️⃣
            for(int i=1;i<=sum.get(0);i++){
                if(sum.get(0)%i==0){
                    n++;                
                }
            }
            6️⃣
            if(n==2){
                answer += 1;
            }
            
            7️⃣
            return;
        }
		
        8️⃣
        for(int i=start;i<arr.length;i++){ 
            if(!visited[i]){
  
                visited[i] = true; 

                combination(arr,visited,i+1,depth+1,r); 

                visited[i] = false; 
            }
        }
    }
}

이번 문제는 소수를 구하는 것보다 조합을 구현하는 부분이 제일 어려웠다.

조합은 서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수로 순서가 달라도 [1,2]와 [2,1]을 동일한 경우의 수로 본다.

1️⃣ Solution클래스 내에서 모두 사용할 수 있도록 static으로 answer를 선언

2️⃣ nums라는 이름의 숫자배열을 매개변수로 받고 서로다른 3가지를 고를것이기 때문에 r을 3으로 대입해준다.

	combination메서드를 호출
		- nums : 주어진 숫자 배열
    	- new boolean : visited / 중복을 방지하기 위한 배열
    	- 0 : start / 현재 선택한 원소보다 뒤에 잇는 원소에 대해서만 탐색하기 위함
    	- 0 : depth / r과 비교하기 위해서
    	- r : 3개씩 뽑을 것
        
3️⃣ 조합으로 구한 경우의 수들의 합을 저장하기위한 List : sum

4️⃣ 만약 depth의 값이 r과 같다면 arr의 길이만큼 반복문을 돌린다.
여기서 visited의 i번째의 값이 true라면 s에 arr의 i번째 값을 더해준다.
그리고 sum에 s를 add해준다.

5️⃣ 그리고 소수여부를 파악하기 위해서 반복문을 돌리고 소수라면 n++을 실행한다.

6️⃣ 이후 n이 2개라면 소수이기에 answer에 +1을 해준다.

7️⃣ for문이 마무리 되거나 if문이 일치하지 않았을 경우 return문으로 나온다.

8️⃣ i를 start부터 arr의 길이까지 반복하면서 만약 visited의 i번재의 값이 false라면 true로 바꿔준다.
그리고 combination 메서드를 재귀호출 한다. 
start의 값은 i+1을 depth의 값도 기존의 depth에 +1을 해주고 호출한다.

재귀호출에서 돌아온 후 i번째의 값을 false로 바꿔준다.

---

💬 다른 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] nums) {
        int ans = 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 ++ ){		
                	🐛
                    if(isPrime(nums[i] + nums[j] + nums[k])){
                        ans += 1;  
                    } 
                }
            }
        }
        return ans;
    }
    public Boolean isPrime(int num){
        int cnt = 0;
        for(int i = 1; i <= (int)Math.sqrt(num); i ++){
            if(num % i == 0) cnt += 1; 
        }
        return cnt == 1;
    }
}

프로그래머스 사이트가 개편되면서 백준허브가 작동하지 않는다...
그래서 실행시간을 확인할 수는 없지만 제출해보면 내 코드로는 13초 14초 훨씬 넘게 나오는것들이 위의 코드로는 10초 안에 끝나더라 ㅎㅎ

isPrime함수는 소수찾기에서 공부했듯이 제곱근을 이용해서 소수여부를 판단한다.

그렇다면 위에 반복문들은 뭘까
🐛가 있는 위치에서 i, j, k의 값들을 출력해보면

i는 0 j는 1 k는 2
i는 0 j는 1 k는 3
i는 0 j는 2 k는 3
i는 1 j는 2 k는 3

i가 0이고 j가 1일때 k의 반복문이 돌고 k반복문이 다 돌면 j반복문이 j가 마무리되면 마지막에 i의 반복문이 마무리된다.

---

👏 마무리

뭐야... 조합 안써도 풀 수 있는 거였어...
조합 너무 어려웠는데

저 코드가 왜 통과인지 알 수 없지만 이왕 이렇게 된거 조합 순열 공부해야지

조합 순열 공부 ❗️