프로그래머스 - 12977번: 소수 만들기 [Java]

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

프로그래머스

1. 코드

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        Arrays.sort(nums);
        
        int len = nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3];
        ArrayList <Integer> arr = new ArrayList<>();
        for(int i = 2; i <= len; i++) {
            if(arr.isEmpty()) arr.add(i);
            else {
                boolean flag = true;
                for(int j = 0; j < arr.size(); j++) {
                    if(i % arr.get(j) == 0) {
                        flag = false;
                        break;
                    }
                }
                if(flag) arr.add(i);
            }
        }
        
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                for(int k = j + 1; k < nums.length; k++) {
                    if(arr.contains(nums[i] + nums[j] + nums[k]))
                        answer++;
                }
            }
        }
        return answer;
    }
}

2. 설명

매번 3개의 수를 합할 때마다 2부터 합한 수까지 진행하여 소수인지 판별하는 방식은 너무 오래걸릴 것 같았기에 최대 크기의 3개의 합까지 진행될 때 소수를 미리 구하는 방식으로 진행됩니다.

int answer = 0;
Arrays.sort(nums);

우선 nums를 정렬하는데 그 이유는 최대로 얼마의 소수까지 판별하는지 확인하기 위함입니다.

int len = nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3];
ArrayList <Integer> arr = new ArrayList<>();
for(int i = 2; i <= len; i++) {
    if(arr.isEmpty()) arr.add(i);
    else {
        boolean flag = true;
        for(int j = 0; j < arr.size(); j++) {
            if(i % arr.get(j) == 0) {
                flag = false;
                break;
            }
        }
        if(flag) arr.add(i);
    }
}

최대의 길이를 nums의 가장 큰 수 3개의 합으로 한 뒤 반복문을 이용하여 len까지 arr에 나누어지지 않는 것은 소수로 판별하고 arr에 추가합니다.

for(int i = 0; i < nums.length; i++) {
    for(int j = i + 1; j < nums.length; j++) {
        for(int k = j + 1; k < nums.length; k++) {
            if(arr.contains(nums[i] + nums[j] + nums[k]))
                answer++;
        }
    }
}

삼중 반복문으로 3개 수의 합을 구한 뒤 arr에 소수로서 저장되었다면 answer 증가시킵니다. 그리고 answer를 반환하면 문제는 해결됩니다.

3. 정리

1. 최대 합까지의 소수 여부를 미리 구한다

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges