[c++] 프로그래머스 - 소수 만들기(Level 1)

문제

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

코드

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

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

    map<int,bool> prime;
    
    for(int i=0; i<=2997; i++) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i=2; i<=2997; i++){  //소수 저장
        if(prime[i]==true){
            int k = 2;
            while(i*k <=2997){
                prime[i*k] = false;
                k++;
            }
        }
    }
    
    for(int a=0; a<nums.size()-2; a++){
        for(int b=a+1; b<nums.size()-1; b++){
            for(int c=b+1; c<nums.size(); c++){
                int check_num = nums[a] + nums[b] + nums[c];
                if(prime[check_num]) answer++;
            }
        }
    }
    

    return answer;
}

풀이(22분)

에라토스테네스의 체를 활용하여 소수를 구하는 문제였습니다. 간단한 문제였는데, 일단 에라토스테네스 알고리즘이 떠오르지 않아서 시간이 좀 걸렸고, 처음 소수를 구하는 과정을 nums에서 고를 수 있는 최고의 경우인 1000+999+998 = 2997만큼 구해야 하는데 1000으로 설정했다가 시간을 좀 까먹었습니다. 여튼 이번 문제를 계기로 에라토스테네스의 체 알고리즘에 대해서 다시 한번 기억해야겠습니다.