99클럽 코테스터디 15일차 TIL 소수찾기

문제 소수찾기

프로그래머스 level 2 완전탐색

문제링크

문제설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

문제풀이

문제 설명이나 구현해야할 것은 명확했지만 그만큼 시간복잡도가 높을 것 같아서 설계하는 단계에서 고민을 많이 한 문제였다.

예상했던 시간복잡도는
에라토스테네스의 체 $O(Nlog(logN))$ + 순열 알고리즘 $n!$
제한사항에서 길이가 최대 7자리 라고 했으니 최대의 N을 10^8 이라 했을 때,
$10^8 * log(8) + 6000(7! + 6! + 5! + 4! + 3! + 2!)$ 정도로 나와 생각보다는 오래걸리지만 아슬아슬하게 통과할 것 이라 생각하고 풀이했다.

소수인지 아닌지 판별을 위해 에라토스테네스의 체를 활용해 가능한 최대 숫자까지의 소수를 체크해주고,

순열 알고리즘을 통해 모든 경우의 수를 체크해 줬다.

또한, 중간에 한번 확인했던 경우를 한번 더 확인하는 경우가 있어 그 부분을 체크할 수 있는 bool array를 하나 추가해 풀이했다.

코드

#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iostream>
#define MAXN 10000003

using namespace std;

bool primes[MAXN], already_checked[MAXN] = {false, }, visited[7];
int res=0;

void init_primes() {
    fill(primes, primes+MAXN, true);
    primes[0] = false;
    primes[1] = false;
    for (int i=2; i<pow(MAXN, 0.5); i++) {
        for (int j=i*i; j<MAXN; j+=i) primes[j] = false;
    }
}

void init () {
    for (int i=0; i<7; i++) visited[i] = false;
}

void dfs (string numbers, string tmp, int depth, int mlen) {
    if (depth == mlen) {
        if (primes[stoi(tmp)] && !already_checked[stoi(tmp)]) {
            already_checked[stoi(tmp)] = true;
            res++;
        }
    }
    for (int i=0; i<numbers.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(numbers, tmp+numbers[i], depth+1, mlen);
            visited[i] = false;
        }
    }
}

int solution(string numbers) {

    init_primes();

    for (int i=1; i<numbers.size()+1; i++) {
        init();
        dfs(numbers, "", 0, i);
    }

    return res;
}

회고

오랫만에 dfs 알고리즘으로 완전탐색을 하려니 좀 해멨었지만, 예전에 많이 했었던 거라서 금방 생각났다.

소수판별 + 완전 탐색을 해야하는 코테에 자주 나오는 두 유형을 합쳐놓은 문제였다.