[프로그래머스/Level 2] 소수 만들기 (C++)

programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

풀이

DFS로 조합 구현하여 문제를 해결하였는데, next_permutation을 이용해 순열로도 문제를 해결할 수 있다.

 

전체 코드

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

int answer;

bool isPrime(int n) {
    if(n < 2) return false;
    for(int i = 2; i < n; i++) {
        if(n % i == 0) return false;
    }
    return true;
}

void DFS(int idx, int cnt, int sum, vector<int> nums) {
    if(cnt == 3) {
        if(isPrime(sum)) answer++;
        return;
    } else {
        for(int i = idx; i < nums.size(); i++) {
            DFS(i + 1, cnt + 1, sum + nums[i], nums);
        }
    }
}

int solution(vector<int> nums) {
    DFS(0, 0, 0, nums); // 인덱스 번호, 고른 수, 누적 합, 벡터
    return answer;
}

 

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

// 소수 판별 함수
bool isDecimal(int sum) {
    bool flag=true;
    for(int i=2;i<=sqrt(sum);i++) {
        if(sum%i==0) {
            flag=false;
            break;
        } 
    }
    return flag;
}

int solution(vector<int> nums) {
    int res=0;
    vector<int> tmp(nums.size(), 1);
    
    // nums의 사이즈가 5일때, 0 0 0 1 1 : 순열의 틀을 만든다.
    for(int i=0;i<3;i++) {
        tmp[i]=0;
    }
    
    // 순열 코드 (정렬 되어 있어야 함)
    do {
        vector<int> v;
        int sum=0;
        for(int i=0;i<tmp.size();i++) {
            // 만든 틀을 기준으로 값을 넣는다.
            if(tmp[i]==0) {
                v.push_back(nums[i]);
            }
        }
        for(int i=0;i<v.size();i++) {
            sum+=v[i];
        }
        // 소수이면 개수 증가
        if(isDecimal(sum)) res++;
    } while(next_permutation(tmp.begin(), tmp.end()));

    return res;
}