프로그래머스 <소수 만들기> C++ 풀이

문제 설명
주어진 숫자 중 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

 

풀이

이 문제에서는 간단하게 소수 구하는 방법만 알면 쉽게 풀어나갈 수 있습니다.

특정한 수가 소수인지 확인하는 함수를 만들고, 3개의 숫자를 조합할 수 있는 로직을 짜면 되는데요.

 

사실상, 참조 테이블을 만들지 않고 해결하기 위해서는 3중 for문을 사용해서, O(N^3) 방식을 선택해야합니다.

반복문 사용 시, 다음과 같은 데이터를 출력할 수 있게 해야합니다.

[1,2,3,4] 가 입력 파라미터 인 경우,

경우의 수	총합
1,2,3	6
1,2,4	7
1,3,4	8
2,3,4	9

총 4개의 경우의 수를 찾을 수 있도록 로직을 짜야합니다.

i = 0 부터 시작, j = i + 1 부터 시작, k = j + 1 부터 시작하게하여, 중복한 경우의 수가 나타나지 않게 하고,

구한 경우의수를 각각 더하여 총합에 대하여 isPrimeNumber 함수를 동작시키고, 만약 소수인 경우 값을 하나씩 + 카운팅 하여 해당 결과를 반환해주면 해당 문제는 풀리게 됩니다.

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

static inline bool isPrimeNumber(int num) {
    if (num == 1) return false;

    int i;
    for (i = 2; i < num; ++i) 
    {
        if (num % i == 0) {

            return false;
        }
    }

    return true;
}

int solution(vector<int> nums) {
    int answer = 0;

    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); ++j) {
            for (int k = j+1; k < nums.size(); ++k) {
                //printf("%d %d %d = %d \n", nums[i], nums[j], nums[k], nums[i] + nums[j] + nums[k]);
                if (isPrimeNumber(nums[i] + nums[j] + nums[k])) {
                    answer++;
                }
            }
        }
    }
   

    return answer;
}

 

---

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

프로그래머스