[JAVA] 프로그래머스 (Lv.1) 소수 만들기

AIR·2023년 8월 27일

코딩 테스트 문제 풀이

목록 보기

13/135

링크

https://school.programmers.co.kr/learn/courses/30/lessons/12977

문제 설명

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

제한 조건

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

입출력 예

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

나의 코드

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

		//배열에서 각자 다른 세 수를 꺼내야 하므로 3중 for문을 돌린다
        //세 수를 더한 값이 소수이면 answer++;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int hap = nums[i] + nums[j] + nums[k];
                    if (isPrimeNumber(hap)) {
                        answer++;
                    }
                }
            }
        }
		
        answer값을 반환
        return answer;
    }
	//소수를 판단하는 메서드를 생성
    public boolean isPrimeNumber(int num) {
        int cnt = 0;
		//1과 자기를 제외한 수 중에서 나누어 떨어지는 수가 있을 경우
        //cnt값을 증가 시킴과 동시에 break
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                cnt++;
                break;
            }
        }
		//cnt값이 그대로 0일 경우 true를 반환
        return cnt == 0;
    }
}

다른 사람의 풀이

class Solution {

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

        for(int i = 0; i < nums.length - 2; i++){
            for(int j = i + 1; j < nums.length - 1; j++){
                for(int k = j + 1; k < nums.length; k++){
                    if(isPrime(nums[i] + nums[j] + nums[k])){
                        ans += 1;  
                    } 
                }
            }
        }
        return ans;
    }
    public Boolean isPrime(int num){
        int cnt = 0;
        for(int i = 1; i <= (int)Math.sqrt(num); i++){
            if(num % i == 0) cnt += 1; 
        }
        return cnt == 1;
    }
}

전체적인 풀이는 동일하나
소수판단 메서드의 for문을 다르게 작성하였다

정리

쉬운 문제였다.
대부분의 테스트 케이스에서도 좋은 속도를 보였으나
일부 케이스의 경우 속도가 느리게 나왔는데 다른 사람의 풀이를 참고하니
소수인지 판단을 할때 for문을 돌리는 범위 값에 따라 달랐다.
나는 for을 num - 1 까지 돌려도 어짜피 break를 걸어놨으니 상관없을거라 생각을 했는데
결국 이건 $O(n)$ 의 시간복잡도를 가진다.
1을 제외한 자연수 중에서 소수를 제외한 수를 합성수라 하는데
예를 들어 64라는 합성수가 있을때 64의 약수는 1, 2, 4, 8, 16, 32, 64 이다.
64는 1x64, 2x32, 4x16, 8x8로 나타낼 수 있다.
여기서 P x Q라 일반화 할때 P는 64의 제곱근 이하, Q는 64의 제곱근 이상 이상이다.
따라서 64는 제곱근인 8이하의 인수는 무조건 가진다 볼 수 있으므로
for문의 범위를 제곱근의 범위까지로 하여도 소수를 판단할 수 있다.
그러면 시간 복잡도는 $O(\sqrt{n})$ 이 된다.

public boolean isPrimeNumber(int num) {
        int cnt = 0;
		//수정한 코드
        //채점결과 속도가 엄청 빨라졌다
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                cnt++;
                break;
            }
        }
        return cnt == 0;
    }