[프로그래머스] 소수 찾기 - c++

소수 찾기

이 문제는 내게 굉장히 복잡했다..

[문제 정의]

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수의 개수를 알아내는 문제이다.

"17" 일 경우 각 종이 조각의 조합은
1, 7, 17, 71 이 되고,

"011" 일 경우 각 종이 조각의 조합은
0, 1, 11, 101, 110 이 된다.

이러한 조합을 중복을 방지하며 candidate라는 변수명을 가진 set에 저장할 것이다.
그리고 한자리 수, 두자리수, .. , numbers.size() 자릿수 크기의 순열을 만들 것 이므로 numbers를 우선 정렬한다.

set<int> candidate;  // 중복 제거용
sort(numbers.begin(), numbers.end());

그 후, select라는 boolean 값을 가진 배열에 기본값은 false로, numbers.size() 만큼의 크기를 배정한다.

for문을 돌며 i개씩 true로 채우고 해당 배열의 순열을 돌 것이다.

처음엔 [false, false, true] (예: 1개 선택) 같은 상태로 시작하고,

next_permutation이 실행될 때마다 select 배열 내 true와 false의 위치가 바뀌면서

[true, false, false], [false, true, false], [false, false, true] 이렇게 모든 조합이 나오게 된다.

즉, i=1일 경우 각각의 종이조각을 다 체크할 수 있게되는 것이다.

vector<bool> select(numbers.size(), false);
fill(select.end() - i, select.end(), true);  // i개 선택

해당 조합의 모든 순열을 생성하여 candidate에 insert형태로 저장한다.

// 길이 1부터 numbers.size()까지 모든 조합 생성
for (int i = 1; i <= numbers.size(); i++) {
    vector<bool> select(numbers.size(), false);
    fill(select.end() - i, select.end(), true);  // i개 선택

    do {
        string sub = "";
        for (int j = 0; j < numbers.size(); j++) {
            if (select[j]) sub += numbers[j];
        }

        // 해당 조합의 모든 순열을 생성
        sort(sub.begin(), sub.end());
        do {
            candidate.insert(stoi(sub));
        } while (next_permutation(sub.begin(), sub.end()));

    } while (next_permutation(select.begin(), select.end()));
}

그 후 cadidate를 돌며 해당 숫자가 소수인지 아닌지 판단한다.

• 소수인지 판별하는 함수

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

모든 경우의 숫자가 소수인지 판별, 소수면 answer++;

 int answer = 0;
    for (int num : candidate) {
        if (isPrime(num)) {
            answer++;
        }
    }

[전체 코드]

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

using namespace std;

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

int solution(string numbers) {
    set<int> candidate;  // 중복 제거용

    sort(numbers.begin(), numbers.end());

    // 길이 1부터 numbers.size()까지 모든 조합 생성
    for (int i = 1; i <= numbers.size(); i++) {
        vector<bool> select(numbers.size(), false);
        fill(select.end() - i, select.end(), true);  // i개 선택

        do {
            string sub = "";
            for (int j = 0; j < numbers.size(); j++) {
                if (select[j]) sub += numbers[j];
            }

            // 해당 조합의 모든 순열을 생성
            sort(sub.begin(), sub.end());
            do {
                candidate.insert(stoi(sub));
            } while (next_permutation(sub.begin(), sub.end()));

        } while (next_permutation(select.begin(), select.end()));
    }

    int answer = 0;
    for (int num : candidate) {
        if (isPrime(num)) {
            answer++;
        }
    }

    return answer;
}