[프로그래머스] 소수 찾기 | C++

문제

프로그래머스

문자열로 주어진 숫자들을 조합하여 그중 소수를 찾아내는 문제이다.

 

나의 풀이 전략

DFS로 완전탐색하여 푼다.

 

상세

1. 우선 소수인지 아닌지 판별하는 함수 isPrime()을 생성한다.

소수라면 1을 반환하도록 했다.

int isPrime(int n)
{
    if (n == 0 || n == 1)
        return 0;

    int squareRoot = sqrt(n); // cmath 라이브러리

    for (int i = 2; i <= squareRoot; ++i)
    {
        if (n%i == 0)
            return 0;
    }

    return 1;
}

 

2. 문자열로 주어진 numbers를 DFS로 완전탐색할 함수 combineNumber()를 선언한다.

combineNumber()의 인수로는 원래 문자열 original, 조합된 문자열 combined, 재귀 깊이 depth로 설정한다.

void combineNumber(string& original, string combined, int depth) // DFS
{

}

 

3. original의 한 문자를 중복해서 사용해선 안되므로 중복방지용 vector<int> 자료형 visited를 선언하자.

또한 combined에 같은 값이 여러번 들어가서도 안된다. set<int> 자료형 numSet을 선언하자.

combineNumber()를 통해 조합된 문자열은 숫자로 변환해 numSet에 넣을 예정이다.

// 전역
vector<bool> visited;
set<int> numSet;

void combineNumber(string& original, string combined, int depth) // DFS
{

}

int solution(string numbers)
{
    int answer = 0;

    visited.assign(numbers.size(), false);

    return answer;
}

 

4. 재귀가 돌고 있다는 가정하에,

combined는 int형으로 변환해 numSet에 집어넣는다.

void combineNumber(string& original, string combined, int depth) // DFS
{
    if(combined.length() > 0)
        numSet.insert(stoi(combined));
}

 

5. original을 일순하면서 사용되지 않은 문자는 combined에 결합시키면서 다음 재귀로 넘긴다.

void combineNumber(string& original, string combined, int depth) // DFS
{
    if(combined.length() > 0)
        numSet.insert(stoi(combined));
    
    for(int i = 0; i < original.size(); ++i)
    {
        if(!visited[i])
        {
            visited[i] = true;
            combineNumber(original, combined + original[i], depth + 1);
            visited[i] = false;
        }
    }
}

 

6. 기저조건을 추가해주자.

예를 들어 original이 "012"라 해보자.

 

depth가 0일 때는 combined = ""이다.

depth가 1일 때는 combined = "0"이다.

depth가 2일 때는 combined = "01"이다.

depth가 3일 때는 combined = "012"이다.

depth가 4일 때는 재귀가 멈춰야 한다.

 

따라서 기저조건은 orignal의 길이를 넘었을 때이다.

void combineNumber(string& original, string combined, int depth) // DFS
{
    if(depth > original.size())
        return;
    
    // ...
}

 

7. solution()을 작성해준다.

int solution(string numbers)
{
    int answer = 0;

    visited.assign(numbers.size(), false);

    combineNumber(numbers, "", 0); // numSet에 조합된 숫자들을 넣음 

    for(int number : numSet)
    {
        if (isPrime(number))
            answer++;
    }

    return answer;
}

 

전체 소스코드

#include <string>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

set<int> numSet;
vector<bool> visited;

int isPrime(int n)
{
    if (n == 0 || n == 1)
        return 0;

    int squareRoot = sqrt(n);

    for (int i = 2; i <= squareRoot; ++i)
    {
        if (n%i == 0)
            return 0;
    }

    return 1;
}

void combineNumber(string& original, string combined, int depth) // DFS
{
    if(depth > original.size())
        return;

    if(combined.length() > 0)
        numSet.insert(stoi(combined));

    for(int i = 0; i < original.size(); ++i)
    {
        if(!visited[i])
        {
            visited[i] = true;
            combineNumber(original, combined + original[i], depth + 1);
            visited[i] = false;
        }
    }
}

int solution(string numbers)
{
    int answer = 0;

    visited.assign(numbers.size(), false);

    combineNumber(numbers, "", 0); // numSet에 조합된 숫자들을 넣음 

    for(int number : numSet)
    {
        if (isPrime(number))
            answer++;
    }

    return answer;
}

 

다른 풀이

사실 내가 문자열을 조합한 방식은

위치별(for 문의 i)로 탐색하여 그 자리에 중복이 있는지 판별하는 등 간접적인 방식이다.

 

그러나 내가 참고한 다른 분의 풀이에는

부분 문자열을 직접 재귀로 넘기는, 보다 직접적인 방식이었다.

void makeCombination(string comb, string others)
{
    // 1. 현 조합을 numberSet에 추가한다.
    if (comb != "")
        numberSet.insert(stoi(comb));

    // 2. 현 조합 + others[i]를 조합하여 새로운 조합을 만든다.
    for (int i = 0; i < others.size(); i++)
        makeCombination(comb + others[i], others.substr(0, i) + others.substr(i + 1));
}

for 문은 others의 i부분만 제외하고 나머지를 다음 재귀의 others로 넘기는 것이다.

이렇게 하면 내가 중복방지용으로 선언한 visited도, 기저조건도 필요없게 된다!

 

굉장히 간단하고 좋은 풀이라 생각한다.