[프로그래머스 c++] 2017 서머코딩 > 소수 만들기

문제 설명

주어진 숫자 중 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

입출력 예 설명

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

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

---

풀이 방법

소수 관련 문제의 대부분은 에라토스테네스의 체 알고리즘이 사용됩니다.

에라토스테네스의 체 알고리즘은 자연수 중 소수를 판별할 수 있게 만드는 알고리즘입니다.

체 알고리즘에 대한 설명은 아래 게시물을 참고해주세요.

https://dvpzeekke.tistory.com/32

[프로그래머스 c++] 소수 찾기

nums 라는 배열에서 3개의 숫자를 조합해 더한 숫자를 addedNums에 집어넣습니다.

addedNums는 조합 과정을 통해 더해진 숫자들이 저장되는 장소로, 후에 각 원소들이 소수인지 아닌지 판별 과정을 거치게 됩니다.

조합 과정은 어마무시한 3중 루프를 이용하게 되는데요.....ㅎ

제한 사항에서 nums 원소의 개수가 50개 이하라고 했으니, 많아도 19,600 번 정도 반복하는 셈입니다.

시간 제한에만 안 걸리면 됐죠 뭐

그리고 루프를 돌면서 addedNums에 속한 값들 중 최댓값을 maxNum이란 변수에 저장해놓습니다.

 

addedNums를 완성하면 체 알고리즘을 통해 addedNums에 있는 값들의 소수 여부를 판단합니다.

먼저 isPrime이라는 벡터를 선언하고, 크기를 maxNum + 1로 지정해 0부터 maxNum 까지의 모든 값들을 소수 여부 판단 대상에 포함시킵니다.

 

체 알고리즘을 통해 2부터 maxNum까지의 소수 여부 판단 과정이 끝나면, isPrime 벡터 안의 값을 참고해 addedNums에 있는 값들이 소수인지 아닌지 확인합니다.

소수일 경우에만 answer의 값을 높혀, 최종적으로 nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 합니다.

 

 

풀이

#include <vector>
#include <iostream>
using namespace std;

int maxNum;

vector<int> addNums(vector<int> &nums) {
    vector<int> addedNums;
    
    // 3개의 숫자 더하기
    // max도 구하기
    for (int i = 0; i < nums.size() - 2; i++) {
        for (int j = i + 1; j < nums.size() - 1; j++) {
            for (int k = j + 1; k < nums.size(); k++) {
                int temp = nums[i] + nums[j] + nums[k];
                
                if (temp > maxNum) {
                    maxNum = temp;
                }
                
                addedNums.push_back(temp);
            }
        }
    }
    
    return addedNums;
}

int solution(vector<int> nums) {
    int answer = 0;
    vector<int> addedNums;
    vector<bool> isPrime;
    
    maxNum = 0;
    
    addedNums = addNums(nums);
    isPrime.assign(maxNum + 1, true);
    
    //에라토스테네스의 체 알고리즘
    for (int i = 2; i <= maxNum; i++) {
        if (isPrime[i] == true) {
            for (int j = 2; i * j <= maxNum; j++) {
                isPrime[i * j] = false;
            }
        }
    }
    
    for (int i = 0; i < addedNums.size(); i++) {
        if (isPrime[addedNums[i]]) {
            answer++;
        }
    }
    
    return answer;
}