[Programmers Level1] 소수 만들기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

[문제 풀이 사이트]

 

프로그래머스

 

[문제 설명]

 

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

 

 

[제한 사항]

 

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

 

[입출력 예]

 

nums	result
[1,2,3,4]	1
[1,2,3,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을 만들 수 있습니다.

 

[문제 풀이]

 

입출력 예시#1를 예시로 설명하려고 합니다.

vector<int> nums = {1,2,3,4} 에서 3개를 뽑아서 만들 수 있는 경우의 수(조합)을 구하려면

 

1. 크기가 n개인 boolean 자료형의 temp vector를 생성

2. temp vector를 n-r개는 false로 채우고, r개는 true로 채움

3. temp vector의 순열을 구함(next_permutation)

4. temp vector의 원소가 true인 경우에만 nums vector의 값을 가져옴

 

조합을 구하는 방법은 위와 같고

조합을 구하고 그 3개의 합이 소수인지 확인하기 위한 함수를 만들었습니다.

소수를 구하는 방법에는 반복문을 사용하서 구하거나, 에라토스테네스의 체의 방법도 있지만

 

반복문을 2부터 시작하여 3개의 합의 제곱근일 때까지로 범위를 설정해두고해당 범위 안에서 나누어 떨어진다면 소수가 아닌 것이고,나누어 떨어지지 않는다면 소수로 판단하여 answer를 1증가 시키도록 코드를 구성했습니다.

 

아래와 같이 next_permutation에 대해서도 정리를 해두었습니다.참고부탁드립니다.

 

[C++ 순열과 조합] next_permutation

 

 

[최종 코드]

 

[GitHub]

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

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

bool isPrime(int number) {
    for (int i = 2; i <= sqrt(number); ++i) {
        if (number % i == 0) {
            return false; // 소수 아님
        }
    }
    return true;
}

int solution(vector<int> nums) {
    sort(nums.begin(), nums.end()); // next_permutation을 사용하기 위해선 오름 차순 정렬해야함
    int answer = 0;
    int len = nums.size();
    vector<bool> selected(len);
    fill(selected.end()-3, selected.end(), true); // 3개를 선택하기 위함
    do {
        int sum = 0;
        for (int i = 0; i < len; ++i) {            
            if (selected[i]) {
                sum += nums[i];
            }
        }

        if (isPrime(sum)) {
            ++answer;
        }
        // 오름 차순으로 정렬이되면 내림 차순으로 조합이 생성됨
    } while (next_permutation(selected.begin(), selected.end()));

    return answer;
}