프로그래머스 소수 만들기

오늘도 프로그래머스 1랩 짜리를 풀었다. 문제 자체가 안어려워서 그냥 첨에 푼대로 슥슥하니까 풀리긴 했다. 그런데 소수를 구하는 방법이라던가, 조합 종류를 구하는 방법들이 좋은게 훨씬 많이 있다는걸 알고있는데도 막 하려니까 잘 안떠올랐다. 저녁먹고 와서는 이 문제를 시간을 대폭 줄이고 더 쉽게 풀 방법을 찾아봐야겠다. 지금은 너무 멍청하다!

 

#include <vector>
#include <iostream>
#include <math.h>

using namespace std;

int check_sosu(int num)
{
    for (int i =2; i< num; i++)
    {
        if(num%i == 0)
            return 0;
    }
    return 1;
}
int solution(vector<int> nums) {
    int answer = -1;
    int i,j,k;
    int cnt = 0;
    int len=  nums.size();
    for (i =0;i< len; i++)
    {
        for (j = i; j< len; j++)
        {
            for(k = j; k < len; k++)
            {
                if (i != j && j!= k && i !=k)
                {
                    if (check_sosu(nums[i]+nums[j]+nums[k]) == 1)
                        cnt++;
                }
            }
        }
    }
    answer = cnt;
    return answer;
}

이거 고쳐보고, 파이썬으로도 항상 했었으니까 파이썬으로도 한번 해볼까 한다!

 

저기서 소수인지 체크할 때 시간을 줄이는 방법 1번으로 num 의 제곱근 만큼만 for문을 돌리면 된다는 게 있다. 

두번째 방법은 에라토스테네스의 체! 한번 구현해볼 생각이다. 

 

#include <vector>
#include <iostream>
#include <math.h>

using namespace std;

int numarr[3002];

void eratos()
{
    for(int i = 2; i <= 3000; i++)
    {
        if (numarr[i] != 1)
        {
            for (int j = 2*i; j <= 3000; j += i)
            {
                numarr[j] = 1;
            }
        }
    }
}

int solution(vector<int> nums) {
    int answer = -1;
    int i,j,k;
    int cnt = 0;
    int len=  nums.size();
    eratos();
    for (i =0;i< len; i++)
    {
        for (j = i; j< len; j++)
        {
            for(k = j; k < len; k++)
            {
                if (i != j && j!= k && i !=k)
                {
                    if (numarr[nums[i] + nums[j] + nums[k]] != 1)
                        cnt++;
                }
            }
        }
    }
    answer = cnt;
    return answer;
}

에라토스테네스 체 방식으로 풀었다. 이게 시간이 제일 얼마 안걸린다고 한다! 그냥 작은수부터 그 배수들을 전부 다 소수가 아니게 체크하는 방식이다. 시간이 제일 얼마 안걸린다. 

 

이번에는 메인함수에서 i,j,k 를 중복없이 선정하는 방법을 더 시간이 안걸리게 하는 방법을 생각해보겠당ㅎㅎ

i,j,k 를 선택하는건 조합(combinations) 랑 같다 즉, n개의 수에서 중복없이 , 순서없이 3개의 수를 고르는 것이다. 

조합 식은 

이 식으로 표현가능하고, 이를 재귀로 구현할 수 있다. 

밑 코드에서 combinations 를 보면, 첫번째로 r == 0 일 때 에라토스테네스의 체로 만들어놓은 소수판별 배열에 조합으로 구한 3개 수의 합을 넣어 소수인지 확인한다. r 값은 3에서 시작해 한 숫자를 선택할 때마다 1씩 감소되어 3개의 수를 다 고르면 0이 된다.

depth == nums.size() 는 만약에 배열의 끝까지 다 탐색했는데도 3개의 숫자를 다 고르지 못한 경우이다. 그냥 리턴해준다. 

마지막 else 에서 저 위의 식을 적용하는데, 만약 지금 depth 의 수를 선택할 거라면, tmp 배열에 해당 수를 넣고 재귀 호출을 할 때 r 값을 1 감소시키고, 저장할 배열 인덱스도 1 증가시킨다. 선택안할 경우 아무것도 저장안하고 depth 만 증가시켜서 재귀해준다.

#include <vector>
#include <iostream>
#include <math.h>

using namespace std;

int numarr[3002];
int cnt = 0;
void eratos()
{
    for(int i = 2; i <= 3000; i++)
    {
        if (numarr[i] != 1)
        {
            for (int j = 2*i; j <= 3000; j += i)
            {
                numarr[j] = 1;
            }
        }
    }
}

void combinations(vector <int> nums, int* tmp, int r, int index, int depth)
{
    if (r == 0)
    {
        if ( numarr[tmp[0] +tmp[1] + tmp[2]] != 1)
            cnt++;
    }
    else if (depth == nums.size())
    {
        return ;
    }
    else
    {
        tmp[index] = nums[depth];
        combinations(nums, tmp, r-1, index+1, depth+1);
        
        combinations(nums, tmp, r, index, depth+1);
    }
}

int solution(vector<int> nums) {
    int answer = -1;
    int tmparr[4];
    eratos();
    combinations(nums, tmparr, 3, 0, 0 );
    answer = cnt;
    return answer;
}

아 이건 쫌 헷갈렸다!