[c++] 프로그래머스 - 소수 찾기(Level 2)

문제

코딩테스트 연습 - 소수 찾기

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

#define MAX 9999999+1
using namespace std;
int visited[MAX];
vector<bool> prime (MAX, true); // true일때 소수

int cnt = 0;

void permutation(string inp, string origin, int index){
    if(inp.length()>origin.length()) return;
    
    string number = inp;
    reverse(number.begin(),number.end());
    while(!number.empty()&&number.back()==0) number.pop_back(); // 0 제거
    reverse(number.begin(),number.end());
    if(!number.empty()&&prime[stoi(number)]&&!visited[stoi(number)]){   //소수라면
        visited[stoi(number)] = 1;  //중복 방지를 위한 방문처리
        //        cout<<"조합: "<< stoi(number)<<'\n';
        cnt++;
    }
    
    
    for(int i=index; i<origin.length(); i++){
        string temp = number + origin[i];
        permutation(temp, origin, i+1);
    }
}
int solution(string numbers) {
    int answer = 0;
    
    prime[0] = false, prime[1] = false;
    for(int i=2; i<=MAX; i++){  //소수를 구하는 에라토스테네스의 체
        if (prime[i] == true) {
            int k = 2;
            while (i * k <= MAX) {
                prime[i * k] = false;
                k++;
            }
        }
    }
    sort(numbers.begin(),numbers.end());   //순열 돌리기 전에는 필수로 정렬해야함
    do{ //순열
        permutation("",numbers, 0);
    }while(next_permutation(numbers.begin(),numbers.end()));
    
    answer = cnt;
    return answer;
}

 

풀이(31분)

먼저 에라토스테네스의 체 알고리즘을 통해서 소수(prime number)를 미리 전부 구해줍니다. 문자열을 순열로 돌려서 조합했을 때 그 수가 소수인지 아닌지를 구분하여 구현했습니다. 완전 탐색 문제였는데, 지금 처음에 next_permutation을 진행하기 전에 정렬을 해줘야 한다는 사실을 깜빡하고 제출했다가 75점이 떠서 이상한 데서 고민하다가 시간을 조금 많이 소비했습니다. 

그리고 아래는 재귀 말고 for문을 이용한 풀이입니다. 속도는 아래가 조금 더 느렸습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

#define MAX 9999999+1
using namespace std;
int visited[MAX];
vector<bool> prime (MAX, true); // true일때 소수

int cnt = 0;

void permutation(string number){
    string temp;
    for(int i=0; i<number.length(); i++){
        if(temp.empty()&&number[i]==0) continue;
        temp+=number[i];
        if(prime[stoi(temp)]&&!visited[stoi(temp)]){
            visited[stoi(temp)] = 1;
            cnt++;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    prime[0] = false; prime[1] = false;
    for(int i=2; i<=MAX; i++){  //소수를 구하는 에라토스테네스의 체
        if (prime[i] == true) {
            int k = 2;
            while (i * k <= MAX) {
                prime[i * k] = false;
                k++;
            }
        }
    }
    sort(numbers.begin(),numbers.end());   //순열 돌리기 전에는 필수로 정렬해야함
    do{ //순열
        permutation(numbers);
    }while(next_permutation(numbers.begin(),numbers.end()));
    
    answer = cnt;
    return answer;
}