프로그래머스: 소수판별기

알고리즘 문제 해결 과정을 기록합니다

September 6, 2025 · 3 min read

문제 개요 #

Source: 프로그래머스 문제 링크
Difficulty: Level 2
Key Concept: Brute Force

접근 방법 #

해당 문제는 문자열의 숫자들을 이용한 순열을 만드는 로직과 소수를 판별하는 로직을 모두 구현해야 하는 문제였습니다. 순열의 경우는 std::next_permutation() 또는 BFS를 이용해서 수의 순열을 만들수 있을거라 생각했습니다. 소수 판별의 경우 에라토스테네스의 체 알고리즘을 이용하였습니다.

시행착오 #

std::next_permutation을 이용하여서 1자리에서 최대 7자리까지 순열을 모두 만드는 로직을 구현하기가 생각보다는 까다로웠습니다. 또한 011과 11이 모두 같은 경우로 봐야 해서 set을 사용하거나 0으로 시작하는 경우는 무시하도록 해야 했습니다.

// 최종 해결 코드
const int LIMIT = 1e7;

set<int> prime_number;
vector<bool> prime_vec(1e7, true);
vector<int> vec;
bool vis[8];
void getPrimeSet(){
    prime_vec[0] = prime_vec[1] = false;
    for(int i = 2 ; i * i <= LIMIT ; ++i){
        if(!prime_vec[i]) { continue; }
        for(int j = i ; j <= LIMIT ; j += i){
            prime_vec[i] = false;
        }
    }
}

void dfs(int length){
    if(vec.size() == length){
        int num = 0;
        for(int i = 0 ; i < vec.size() ; i++){
            num = num * 10 + vec[i];
        }
        if(prime_vec[num]){
            prime_number.insert(num);
        }
        return;
    }

    for(int i = 0 ; i < numbers.length ; i++){
        if(!vis[i]) { continue; }
        vis[i] = true;
        vec.emplace_back(numbers[i]);
        dfs(length);
        vec.pop_back();
        vis[i] = false;
    }
    return;
}

int solution(string numbers){
    getPrimeSet();
    for(int i = 1 ; i <= numbers.size() ; i++){
        dfs(i);
    }
}

getPrimeSet을 통해 먼저 vector<bool>에 소수이면 true값을 소수가 아니면 false 값을 할당하였습니다. 이후 dfs를 이용하여 길이가 1~최대 7자리까지 문자열을 이용한 순열을 생성 후 소수 판별을 하여 소수가 맞다면 prime_number set에 넣었습니다. 이 때, 011과 11은 모두 같은 수로 취급되는데 set을 이용해서 중복을 제거하였습니다.

해결 방법 #

위의 방법으로도 테스트는 토오가 하였지만 최적화 시킬 수 있는 부분들을 찾아 수정하였습니다.

소수 판별을 1e7까지 벡터에 할당하지 않고 들어온 수 만큼만 에라토스테네스의 체를 적용 시켰습니다.
vis 배열 사용 대신 비트마스킹을 이용해 메모리 관리를 더욱 효율적으로 변경하였습니다.

알고리즘 설명 #

#include <set>
#include <vector>
#include <string>

using std::set;
using std::vector;
using std::string;

string numbers;
set<int> prime_set;


bool isPrime(int n){
    if(n <= 1) {return false;}
    if(n == 2) { return true;}
    if(n % 2 == 0){ return false;}
    for(int i = 3; i * i <= n ; i+= 2){
        if(n % i == 0) return false;
    }
    return true;
}

void getPrimeNumSet(int mask, int current, int depth){
    if(depth > 0 && isPrime(current)){
        prime_set.insert(current);
    }

    for(int i = 0 ; i < numbers.size(); i++){
     	if(mask & (1 << i)) {continue;}
        int digit = numbers[i] - '0';
        if(current == 0 && digit == 0) { continue;}
        getPrimeNumSet(mask | (1 << i), current * 10 + digit, depth+1);
    }
    return;
}


int solution(string numbers) {
    ::numbers = numbers;
    getPrimeNumSet(0,0,0);
    return prime_set.size();
}

성능 분석 #

첫 번째 방법 (에라토스테네스의 체 + DFS):

Time Complexity: $O(N \log \log N)$
Space Complexity: $O(N)$

두 번째 방법 (비트마스킹 + 즉시 소수판별):

Time Complexity: $O(K! × \sqrt{n})$
Space Complexity: $O(K!)$

핵심 정리 #

경우의 수가 적고 정확한 연산이 필요한 문제의 경우 빠른 완전 탐색의 구현의 정요성을 알 수 있었습니다.

Pelikan's Glide