[코테/JAVA] Summer/Winter Coding(~2018) : 소수 만들기

2022.03.06

85번째 포스팅

 

입사 363일차.

코테 문제풀이 15주차 1번 문제

 

 

0. 문제

  ① Summer/Winter Coding(~2018) : 소수 만들기

  ② 설명

문제설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

  ③ 링크

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

 

 

1. 접근방법

  생각해낸 방법은 2가지

  ① 3차원배열

  ② dfs 재귀호출

 

 

2. 풀이

  ① 접근방법 : ②

  ② 풀이

import java.util.*;
 
class Solution {
    /*
     * Date 2022-03-06
     * Time 22:10
     */
    
    /*
     * 전역변수선언
     * 1. int[] numArr(= nums)
     * 2. HashSet set 중복여부체크
     * 3. int answer 소수갯수
     */
    public static int[] numArr;
    public static HashSet<Integer> set;
    public static int answer = 0;
    
    public int solution(int[] nums) {
        numArr = nums;
        set = new HashSet<>();
        dfs(0, 0, 0);
        return answer;
    }
    
    /*
     * 메소드명: chckPrimeNumber
     * 파라미터로 들어온 숫자의 소수여부판별
     */
    public void chckPrimeNumber(int number) {
        if (number < 2) {
            return;
        }
        int sqrtNum = (int)Math.sqrt(number);
        for (int i = 2; i <= sqrtNum; i++) {
            if (number % i == 0) {
                return;
            }
        }
        answer++;
    }
    
    /*
     * 메소드명: dfs
     * 완전탐색
     */
    public void dfs(int size, int depth, int sumNum) {
        /*
         * Validation
         * 3개의 수를 더한 경우
         * 1. 소수판별
         * 2. return
         */
        if (size == 3) {
            chckPrimeNumber(sumNum);
            return;
        }
        
        /*
         * Validation
         * 재귀의 횟수가 고정배열의 length와 같아질 경우
         * 1. return
         */
        if (depth == numArr.length) return;
        
        /*
         * 재귀시작
         * 1. 다음 index를 차례대로 더하며 재귀호출 (depth + 1)
         * 2. nums.length가 3보다 큰 경우, 다음 index를 건너뛰면서 재귀호출 (depth)
         */
        dfs(size + 1, depth + 1, sumNum + numArr[depth]);
        dfs(size, depth + 1, sumNum);
    }
}

 

 

3. 결과

 

 

4. 주의사항

  ① 중복제거를 해서는 안된다 (1 + 2 + 8와 1 + 3 + 7은 같은 11로 소수이지만 각각의 개수로 쳐줘야한다.)