[Algorithm] 소수 만들기

Jay·2021년 2월 2일

Algorithm

목록 보기

22/44

문제 설명

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

제한사항

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

입출력 예

nums [1,2,3,4]
result 1

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

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

처음에 접근하기

왜인지.. 당연하단듯이 순열로 접근했다.. 사실은 중복을 무시해야 하는데..
그래서 다 적고 나서 아?! 그럼 그냥 나온 데이터들을 더 하면 하나의 값으로 귀결되니까 그게 겹치는 지 판단해서 소수인지 판단해서 set에 넣어두자 했지만..

import java.util.*;

class Solution {
    static Set<Integer> set = new HashSet<>();
    
    public int solution(int[] nums) {
        doPermutation(nums, 0, 3);
        return set.size();
    }
    
    public void doPermutation(int[] arr, int depth, int r){
        if(depth==r){
            int num = 0;
            for(int i=0; i<r; i++){
                num += arr[i];
            }        
            if(!set.contains(num)){
                if(isPrime(num)){
                    System.out.println(String.valueOf(num));
                    set.add(num);
                }
            }
            
        }else{
            for(int i=0; i<arr.length; i++){
                swap(arr, depth, i);
                doPermutation(arr, depth+1, r);
                swap(arr, depth, i);
            }
            
        }
    }
    
    public void swap(int[] arr, int depth, int i){
        int tmp = arr[i];
        arr[i] = arr[depth];
        arr[depth] = tmp;
    }
    
    public boolean isPrime(int num){
        int sqrt_num = (int)Math.sqrt(num);
        boolean flag = true;
        if(num==2){
            flag = true;
        }else if(num%2==0 || num==1){
            flag = false;
        }else{
            for(int i=3; i<=sqrt_num; i+=2){
                if(num%i==0){
                    flag = false;
                }
            }
        }
        return flag;
    }
}

새롭게 접근하기

그래 새롭게 접근하다 생각하고 조합으로 갔다.
근데 너무 안풀리길래 보니까 순열과 조합을 쓰지도 않는 문제였다.

import java.util.*;

class Solution {
    static Set<Integer> set = new HashSet<>();
    
    public int solution(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];
        
        doCombination(nums, visited, 0, 3);
        
        return set.size();
    }
    
    public static void doCombination(int[] arr, boolean[] visited, int depth, int r){
        if(r==0){
           print(arr,visited);
           return;
        }
        if(depth==arr.length){
            return;
        }else{
            visited[depth] = true;
            doCombination(arr, visited, depth+1, r-1);
            
            visited[depth] = false;
            doCombination(arr, visited, depth+1, r);
        }
    }
    
     // 배열 출력
    static void print(int[] arr, boolean[] visited) {
        int result = 0;
        for(int i = 0; i < arr.length; i++) {            
            if(visited[i] == true){
                result += arr[i];
            }
        }
        if(!set.contains(result)){
            if(isPrime(result)){
                set.add(result);
            }
        }
    }
    
    static boolean isPrime(int num){
        int sqrt_num = (int)Math.sqrt(num);
        boolean flag = true;
        if(num==2){
            flag = true;
        }else if(num%2==0 || num==1){
            flag = false;
        }else{
            for(int i=3; i<=sqrt_num; i+=2){
                if(num%i==0){
                    flag = false;
                }
            }
        }
        return flag;
    }
}

정답 코드

3중 for문을 이용해서 푸는 거였다..
너무 어렵게 생각했나보다..

import java.util.*;

class Solution {
    
    public int solution(int[] nums) {
        int n = nums.length;
        int count = 0;
        
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int k=j+1; k<n; k++){
                    int sum = nums[i]+nums[j]+nums[k];
                    if(isPrime(sum)){
                        count++;   
                    }
                }
            }
        }
        
        return count;
    }
    
    
    static boolean isPrime(int num){
        int sqrt_num = (int)Math.sqrt(num);
        boolean flag = true;
        if(num==2){
            flag = true;
        }else if(num%2==0 || num==1){
            flag = false;
        }else{
            for(int i=3; i<=sqrt_num; i+=2){
                if(num%i==0){
                    flag = false;
                }
            }
        }
        return flag;
    }
}