Programmers] 소수 만들기

 

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

[제한사항]

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

[입출력 예]

 

 

---

추측) 

소수의 개념은 1과 그 값 자체만 약수로 가지는 수다. 

일단 nums에서 3개의 수를 골라 더하는 경우의 수를 구하려면 for문이 3개나 돌아야하는 데 너무 비효율적이다.

다른 방법이 있을거라 생각한다. 일단은 for문으로 구현 먼저 해보고 검색해서 개선하는 방향으로 가자

 

소스코드) 

* 1차) 실패 - 역시나 효율성이 너무 안좋아서 메모리 초과, 런타임 에러 등등 다양한 실패로 테스트에서 단하나 통과한 케이스

import java.util.ArrayList;

class Solution {
   public int solution(int[] nums) {
        int sum = 0;

        // 이 숫자의 개수로 만들수 있는 전체 경우의 수
        int caseCnt = 0;
        for (int x=0; x<3; x++){
            if(x==0){
                caseCnt = nums.length;
                continue;
            }
            caseCnt *= nums.length-x;
        }

        // 이 숫자들 중 3개 값의 합을 해당 인덱스에 넣기 (중복은 피한다)
        int[] flagArr = new int[caseCnt];
        for(int i=0; i<nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                for(int k=j+1; k< nums.length; k++){
                    if(flagArr[nums[i] + nums[j] + nums[k]] == 1){
                        continue;
                    }
                    flagArr[nums[i] + nums[j] + nums[k]] = nums[i] + nums[j] + nums[k];
                }
            }
        }

        // 합의 경우의 수만 모으기
        ArrayList<Integer> sumCase = new ArrayList<>();
        for(int y=0; y<flagArr.length; y++){
            if(flagArr[y] != 0){
                sumCase.add(flagArr[y]);
            }
        }

        // 소수를 어떻게 가리나
        int primeNumCnt = 0;
        int numCnt = 0;
        for(int z=0; z<sumCase.size(); z++){
            int sumOne = sumCase.get(z);
            for(int a=2; a<sumOne; a++){
                double share = (double) sumOne / a;
                if(share - (int) share == 0) {
                    numCnt++;
                }
            }
            if(numCnt == 0){
                primeNumCnt++;
            }
            numCnt=0;
        }

        return primeNumCnt;

    }
}

* 2차) 실패 

public int solution(int[] nums) {
    int sum = 0;

    int numsLen = nums.length;

    // 중복 값을 피하기위한 배열 생성
    Arrays.sort(nums);
    int[] numArr = new int[nums[numsLen-1]+nums[numsLen-2]+nums[numsLen-3]+1];

    // for문을 돌릴 횟수는 nCr로 구한다.
    int sumCaseFull = (numsLen*(numsLen-1)*(numsLen-2)) / 6; // 조합 공식 nCr = nPr/r!  // n숫자개수 r선택개수
    for(int i=0; i<numsLen; i++){
        for(int j=i+1; j<numsLen; j++){
            for(int k=j+1; k<numsLen; k++){
                if(numArr[nums[i] + nums[j] + nums[k]] == nums[i] + nums[j] + nums[k]){
                    continue;
                }
                numArr[nums[i] + nums[j] + nums[k]] = nums[i] + nums[j] + nums[k];
            }
        }
    }

    // 합의 경우의 수만 모으기
    ArrayList<Integer> sumCase = new ArrayList<>();
    for(int y=0; y<numArr.length; y++){
        if(numArr[y] != 0){
            sumCase.add(numArr[y]);
        }
    }

    // 소수를 어떻게 가리나
    int primeNumCnt = 0;
    int numCnt = 0;
    for(int z=0; z<sumCase.size(); z++){
        int sumOne = sumCase.get(z);
        for(int a=2; a<sumOne; a++){
            if(sumOne%a == 0) {
                numCnt++;
            }
        }
        if(numCnt == 0){
            primeNumCnt++;
        }
        numCnt=0;
    }
    return primeNumCnt;
}

* 3차) 성공 [메모리: 82.8 MB, 시간: 0.03 ms]

public int solution(int[] nums) {
    int sum = 0;
    int numsLen = nums.length;

    // for문을 돌릴 횟수는 nCr로 구한다.
    ArrayList<Integer> sumArr = new ArrayList<>();
    int sumCaseFull = (numsLen*(numsLen-1)*(numsLen-2)) / 6; // 조합 공식 nCr = nPr/r!  // n숫자개수 r선택개수
    for(int i=0; i<numsLen; i++){
        for(int j=i+1; j<numsLen; j++){
            for(int k=j+1; k<numsLen; k++){
                sumArr.add(nums[i] + nums[j] + nums[k]);
            }
        }
    }

    // 소수를 어떻게 가리나
    int primeNumCnt = 0;
    int numCnt = 0;
    for(int z=0; z<sumArr.size(); z++){
        int sumOne = sumArr.get(z);
        for(int a=2; a<sumOne; a++){
            if(sumOne%a == 0) {
                numCnt++;
            }
        }
        if(numCnt == 0){
            primeNumCnt++;
        }
        numCnt=0;
    }
    return primeNumCnt;
}

 

리뷰) 

 

1차) 오로지 알고있는 한도내에서 구현한 코드. 일단 경우의 수를 구하는 공식도 틀렸고 효율성이 너무 안좋다 생각이 들어서 통과할거란 생각은 안했다. 일단 입출력 예의 result를 출력해 낼 수 있는가만 생각해봤다.

2차) 조합 공식을 알게 되었다 (지식+1) 조합 공식을 이용해 경우의 수를 구해 적용했다.

3차) 아니!!!! 합의 수가 같은건 일부러 제외했는데 ㅠㅠㅠㅠㅠ 오히려 중복을 제거하면 안됬던 거였다 ㅠㅠㅠ 문제를 잘보자 ㅠㅠㅠ 

 

 

 

 

+ 조합 알고리즘:

[알고리즘 - 조합] 조합과 조합 알고리즘

정승제 쌤의 조합 강의 :