Sohn SooKyoung

💛💚

최대 1 분 소요

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package _1월_2주차;
 
import java.util.Scanner;
 
public class 프로그래머스_손수경_정답_소수만들기 {
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int[] nums = new int[50];
        int cnt = sc.nextInt();
        int temp;
        int ans = 0;
        
        for (int i = 0; i < cnt; i++) {
            nums[i] = sc.nextInt();
        }
        //차피 3개만 뽑아서 구하는 것이므로 가능한 풀이,,,
        for (int i = 0; i < cnt; i++) {
            for (int j = i + 1; j < cnt; j++) {
                for (int k = j + 1; k < cnt; k++) {
                    temp = (nums[i] + nums[j] + nums[k]);
 
                    if (isPrimeNum(temp) == true) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
    
    public static boolean isPrimeNum(int num) {
        int n = (int)Math.sqrt((double)num);
        int i;
        boolean isPrimeNum = true;
        //입력값 중 중복이 없고, 입력값은 자연수이므로 2, 3이 나올 수 없다. -> 따로 처리해주지 않아도 됨.
        for (i = 2; i <= n; i++) {
            if (num % i == 0) {
                isPrimeNum = false;
            }
        }
 
        return isPrimeNum;
    }
}
cs


이 문제와 비슷한 것을 예전에 파이썬을 통해서 구현해본 적이 있다. 하지만 그 문제에서는 리스트에서 몇개를 뽑을 것인지까지 입력받았기 때문에 재귀함수를 썼었던 것으로 기억을 한다.(매우 어려웠었음,,) 여튼 하지만 이 문제의 경우는 배열에서 “3개”를 뽑는 것으로 문제에서 나와있으므로 삼중 루프를 돌려서 구해주었다. 소수를 구하는 함수인 isPrimeNum 은 num의 제곱근을 구한 만큼 반복문을 돌면서 나누어 떨어지는지 아닌지를 판별하는 함수이다. num까지 반복문을 돌려도 되지만 제곱근만큼 돌려도 판별할 수 있으므로 더 효율적임을 알 수 있다.

댓글남기기

참고