[프로그래머스]코딩테스트 연습 Summer/Winter Coding(~2018) 소수 만들기

안녕하세요! 오늘은 프로그래머스 소수만들기를 풀어봤습니다!

 

레벨 1인데 30분이나 걸려 버렸네요 아직 초보인가봐요 ㅠㅠㅠ

 

우선 소수인지 확인하는 함수는 굉장히 쉽습니다!

 

보통 자기와 1을 제외한 수로 나눴을때 딱떨어지지 않으면 소수인데요!

 

굳이 다나눠볼 필욘없고 자기/2 + 1 까지만 나눠봐도 확인이 가능합니다! 다들 이유는 아실거라고 생각할게요!

 

그리고 재귀함수를 이용해서 중복없이 숫자를 만들어야하는데요

 

이부분에서 자꾸 에러가 발생해 오래걸렸습니다 ㅠㅠㅠ

 

원래는 함수 인자도 두개였는데 제가 능력이 모자라 4개까지 늘어버렸네요 ㅠㅠㅠ

 

벡터도 사실 포인터로 가져가는게 좋지만 귀찮아서... ㅎㅎ 죄송합니다!

 

---

코드 한번 같이 보시죠!

 

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

vector<int> results;
bool isUsingNum[51] = {0,};

bool isPrimeNumber(int target) {
    bool res = true;
    for(int i = 2; i < target/2+1; i++) {
        if (target % i == 0) {
            res = false;
            break;
        }
    }
    return res;
}

void makeNumber(vector<int> nums, int cnt, int starting, int result) {
    int size = nums.size();
    
    if (cnt == 3){
        results.push_back(result);
        return;
    }
    
    for (int i = starting; i < size; i++) {
        if (isUsingNum[i] == false) {
            isUsingNum[i] = true;
            cnt++;
            result += nums[i];
            makeNumber(nums, cnt, i+1, result);
            isUsingNum[i] = false;
            cnt--;
            result -= nums[i];
        }
    }
    
}

int solution(vector<int> nums) {
    int answer = 0;
    int size = nums.size();
    int result = 0;
    
    makeNumber(nums, 0, 0, 0);
    
    size = results.size();
    
    for (int i = 0; i < size; i++){
        if (isPrimeNumber(results[i])){
            answer++;
        }
    }
    
    return answer;
}

 

이상입니다!

 

 

※추가로 결과에서 1~16번째까지 실패한다면 꼭 확인해보실게 있습니다! 중복확인이에요! for문 체크해보시기 바랍니다!