프로그래머스 : Summer/Winter Coding 소수 만들기 [C++]

문제 링크

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

 

문제 설명

1. 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다.
2. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때
3. nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 구하시오.

 

문제 입출력 예)

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

 

문제 풀이 (1/2)

nums으로 주어진 인자 중 3개를 골라 소수인지 확인을 해야 하기 때문에

3중 for문을 돌려 모든 경우의 수를 골라내야 한다고 생각했다.

모든 경우의 수를 찾은 다음, 그 숫자가 소수가 맞는지 아닌지만 판단하면 되는 문제였다.

내가 아는 소수인지 확인하는 방법은 3가지 방법이 존재한다.

 

1. for문으로 전부다 돌려서 확인하기.

2. sqrt(num) 까지만 돌려서 확인하기.

3. 에라토스테네스의 체를 이용하기.

#include <vector>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool is_prime(int num){
    if(num <= 1)
        return false;
    if(num == 2 || num == 3)
        return true;
    for(int i=2; i<=sqrt(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 z=j+1; z<nums.size(); z++){
                int num = nums[i]+nums[j]+nums[z];
                if(is_prime(num) == true ){
                    answer++;
                }
            }
        }
    }

    return answer;
}

위와같은 방법을 이용했을 경우 최소 0.01ms ~ 최대 0.81ms까지 시간이 걸렸다는 것을 볼 수 있다.

이보다 더 빠른 에라토스테네스 체를 이용해보도록 하자.

 

문제 풀이 (2/2)

이번에는 에라토스테네스의 체를 이용해보도록 하였다.

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

int solution(vector<int> nums) {
    int answer = 0;
    vector<bool> v(3000, true);
    
    for(int i=2; i<=v.size(); i++){
        if(v[i] == true){
            for(int j=2; i*j<=v.size(); j++){
                v[i*j] = false;
            }
        }
        
    }
    
    for(int i=0; i<nums.size(); i++){
        for(int j=i+1; j<nums.size(); j++){
            for(int z=j+1; z<nums.size(); z++){
                int num = nums[i]+nums[j]+nums[z];
                if(v[num] == true ){
                    answer++;
                }
            }
        }
    }

    return answer;
}

 

최소 0.02ms~ 최대 0.04ms 속도가 정말 차이나는 것을 볼 수 있다.

가급적이면, 에라토스테네스 체를 이용할 수 있도록 연습하자.

 

리뷰

소수를 판별하는 방법을, 에라토스테네스 체와 for문을 이용한 방법을 사용해봤다.

구현방법은 조금 더 어렵더라도, 에라토스테네스 체가 빠른걸 느낄 수 있었다,