[Java] 프로그래머스 소수 만들기 자바

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12977

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

---

 

[나의 풀이]

- 반복문 중첩을 통해 3개의 수를 선택하여 합

- chkSum 함수로 자기 자신보다 작은 수로 나누어 떨어지지 않을 경우 소수로 판별하여 true return!

- chkSum 함수가 true retrun 일 때만 +

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int tmp1, tmp2, tmp3;
        int sum = 0;

        for(int i=0; i<nums.length-2; i++){ //첫번째 수 선택
            tmp1 = nums[i];
            for(int j=i+1; j<nums.length; j++){	//두번째 수 선택
                tmp2 = nums[j];
                for(int k=j+1; k<nums.length; k++){ //세번째 수 선택
                    tmp3 = nums[k];
                    sum = tmp1 + tmp2 + tmp3;
                    if(chkSum(sum) == true)
                        answer++;
                }
            }
        }
        return answer;
    }

    //3개의 수 합보다 작은 수로 나눴을 때 0으로 떨어지지 않을때 true return
    private boolean chkSum(int sum) {
        for(int l=2; l<sum; l++){
            if(sum%l == 0) return false;
        }
        return true;
    }
}

재귀 함수까지는 아니지만,

반복해서 사용하는 부분에 대해서 함수로 분리해 봤다.(현실은 섬멀티 for문...ㅎㅎㅎ)

반복문이 낭자하는 이 코드...

다른 분들은 또 어떻게 했을까?!?!?

 

[다른 사람의 풀이]

public class Solution{ 
    public static int result = 0;
    public int solution(int[] nums) {
         int answer = 0;
         int n = nums.length; //n=4
         int r = 3;  
         int[] arr = new int[n];
         //combination(배열변수, 인덱스, 입력배열길이, 고르는 숫자개수, 입력배열용 인덱스, 입력배열)
         combination(arr, 0, n, r, 0, nums);
         answer = result;
         return answer;
    }
    
    public static void combination(int[] arr, int index, int n, int r, int target, int[] nums) {
        if (r == 0)             //입력 배열 nums에서 숫자 3개를 고름
            print(arr, index);
        else if (target == n)
            return;
        else {
            arr[index] = nums[target];
            combination(arr, index + 1, n, r-1, target + 1, nums);
            combination(arr, index, n, r, target + 1, nums);
        }
    }
    
    public static void print(int[] arr, int length) {
        int cnt = 0;
        boolean isPrime = false;
        for (int i = 0; i < length; i++) {
            cnt += arr[i];
        }
        // 1과 num 자신 외에 나누어지는 수가 있는지 검사할 조건문
        for (int i = 2; i < cnt; i++) {
            if (cnt % i == 0) {
                // 나누어 떨어지는 경우 isPrime의 값 = true
                // 한 번이라도 이 조건문이 실행될 경우 num은 소수가 아니므로 반복문을 빠져나온다.
                isPrime = true;
                break;
            }
        }
        if (!isPrime) result++;
    }
}

이번 다른 사람의 코드는 조합(Combination)의 개념을 이용한 재귀 함수 방식이다!

중/고등학교 때 배운 수학 개념이기에 오랜만에 구글링을 하며 다시 되짚어 본다....

 

조합(Combination) : n개의 원소에서 r개의 원소를 순서 상관없이 뽑는 경우의 수

[공식]

nCr = nPr / r!

       = n! / (n-r)! * r!

       = n-1Cr-1 + n-1Cr

진하게 표시되었듯, 여기서 핵심은 마지막 줄의 공식이다!

 

[정리]

- 알고리즘 문제에서 소수의 개념은 자주 나오니 반복문을 이용하여 자기 자신만 나눠 떨어지는 수 기억할 것!

- 반복문과 조건문이 복잡해지거나, 빈번하게 사용되는 부분은 함수로 꼭 분리해주는 습관을 들이자!

- 반복문을 반복해서 사용하기보다, 재귀 함수를 이용하여 사고하는 방식도 꾸준히 연습할 것!

 

개인피셜 난이도 : ★★☆☆☆

반복문이 중첩이 되는 것을 보고 재귀 함수를 써야 한다는 건 알았지만,

다른 분이 코딩한 소스처럼 해야겠다는 알고리즘 사고가 떠오르지 않았다...

심지어 지금도 동작 로직이 잘 이해가 되지 않는 상태!.....

(혹시나 지나가다가 말로 잘 표현해주실 분 댓글로 남겨주시면 정말 감사하겠습니다!ㅜㅜ)

이해가 되는대로 조만간 수정하여 업로드하도록 하겠다!....

 

끝!

 

* 참고 블로그

- 조합(Combination) 개념 : https://woongsios.tistory.com/179

Combination 조합

- 조합 로직 예제 : https://minhamina.tistory.com/38

[Java] 조합 Combination