Programmers 문제 12977번 소수 만들기

Programmers 문제 12977번 소수 만들기

---

해당 문제는 다음 링크에서 가져왔습니다. 

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

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

---

저는 이 문제를 구상하는 과정에서 깔끔하게 표현할 수 있는 알고리즘이 생각나질 않았습니다.

때문에 1000이하의 중복이 없는 숫자 3개의 최대합은 998 + 999 + 1000 으로 2997이하의 숫자 중 소수를 찾는 문제라고 접근했습니다. 소수를 만들기 위해서 다음 블로그의 내용을 참고하였습니다. 

https://blog.naver.com/therich21/222533155552

파이썬 소수 판별/출력 프로그램_시간복잡도

일반적인 방법으로 생각할 때에 그냥 모든 경우의 수를 봐서 찾으면 되겠다 싶었지만 더 효과적으로 표현할 수 있는 방법이 존재했습니다.

약수의 특성상 소수를 구할 때에는 $ \sqrt{number} $까지만 나눠보면 된다는 것을 알 수 있다.

더 좋은 시간복잡도로 통과하는 모습을 볼 수 있었습니다.

---

다음은 실행 코드입니다. 

#include <vector>
#include <iostream>
#include <cmath>

#define MAXNUM 2997

using namespace std;

// 최대 합은 998 + 999 + 1000 = 2997
bool prime_numbers[MAXNUM+1] = {false, } ;

bool calculate_a_prime_number(int num){
    for(int i = 2 ;i <= int(sqrt(num)) ; i++)
        if(num % i == 0)
            return false ;
    return true ;
}

void make_an_prime_numbers(){
    for(int num = 2 ; num <= MAXNUM ; num++)
        prime_numbers[num] = calculate_a_prime_number(num) ;
}


int solution(vector<int> nums) {
    int answer = 0 ;
    
    make_an_prime_numbers() ;
    
    for(vector<int>::iterator n1 = nums.begin() ; n1 != nums.end() ; n1++)
        for(vector<int>::iterator n2 = n1+1 ; n2 != nums.end() ; n2++)
            for(vector<int>::iterator n3 = n2+1 ; n3 != nums.end() ; n3++)
                if(prime_numbers[*n1 + *n2 + *n3])
                    answer += 1 ;
    
    return answer;
}

 

해당 코드는 다음 github에서도 볼 수 있습니다.

https://github.com/gurcks8989/CodingTest/blob/master/Programmers/12977_make_a_prime_number.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

 

훈수, 조언 언제나 환영입니다.