✨Link 소수만들기

🤔 문제

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

입출력 예

nums: [1,2,7,6,4]
result: 4

💡 접근

* 코드(1) 시간초과 ❌실패❌
재귀함수를 통해 1. (조합) 서로 다른 3개를 골라 2. 합이 소수가 되는지 판별해 주었다. . 재귀함수는 시간이 많이 걸려서인지 반 정도 시간초과로 실패를 했다..😥

* 코드(2)
3중 for문을 통해 서로 다른 3개의 수를 선택한 후, 더해서 소수를 판별해 주었다.

💻 코드(1)_나의 풀이

class Solution {
    public static int cnt;
	public static List<Integer> list;
    
    public int solution(int[] nums) {
        cnt=0;
    	list=new ArrayList();
    	
    	dsf(nums,0);
        
        return cnt;
    }
    
    public static void dsf(int[] nums, int idx) {
		if(list.size()==3) {//3개 고르면 소수를 판별해주기
			if(calc(list.get(0)+list.get(1)+list.get(2))){
				cnt++;
				return;
			}
		}
		
		for(int i=idx;i<nums.length;i++){
			list.add(nums[i]);
			dsf(nums,i+1);
			list.remove(list.size()-1);
		}
	}
	//소수판별
	public static boolean calc(int sum) {
		int cnt=0;
		
		for(int i=1;i<=sum;i++) {
			if(sum%i==0) {
				cnt++;
			}
		}
		if(cnt==2) {
			return true;
		}else {
			return false;
		}
	}
}

• 3개의 숫자를 선택할때, 순서가 없는 조합을 생각해서 구현해주었다.

• list에 값을 넣어주고 dsf()함수가 리턴될 때, 꼭 list에서 값을 빼주어야 한다!

💻 코드(2)_나의 풀이

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

        for(int i=0;i<=nums.length-3;i++){
            for(int j=i+1;j<=nums.length-2;j++){
                for(int k=j+1;k<=nums.length-1;k++){
                    if(calc(nums[i]+nums[j]+nums[k])){
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
    
    public static boolean calc(int sum){

        int cnt=0;

        for(int i=1;i<=sum;i++){
            if(sum%i==0){
                cnt++;
            }
        }
        if(cnt==2){
            return true;
        }else{
            return false;
        }
    }
}

• 3개의 숫자를 선택할때, 선택했던 숫자는 선택하지 않도록 +1씩 증가하면서 자리가 뒤로 갈수록 선택할수 있는 숫자는 하나씩 줄어간다!