문제

https://programmers.co.kr/learn/courses/30/lessons/42839

아라비아 숫자로만 이루어진 string을 받았을 때, string 안에 각 숫자들의 조합으로 만들 수 있는 모든 소수의 개수를 찾는 문제다.

---

접근

문제를 그대로 코드로 풀어내기만 하면 되는 brute force 알고리즘이다.

1. string안에 있는 모든 숫자의 조합을 구한다
2. 각 숫자가 소수인지 확인한다

라는 아주 간단한 아이디어지만, 늘 그렇듯 brute force는 머리로는 풀기 쉬워도 구현 과정에서 문제가 생기기 쉽다.

---

코드 구현

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

using namespace std;

int solution(string numbers) {
    int answer = 0;
    set<int> numbers_int;

    int len = numbers.length();
    
    for (int i = 1; i <= len; i++) {
        vector<bool> numberlength(len - i, false);
        numberlength.insert(numberlength.end(), i, true);
        
        do {
            string temp = "";
            for(int j = 0; j < len; j++) {
                if(numberlength[j]) temp += numbers[j];
            }
            
            sort(temp.begin(), temp.end()); //<-- 굉장히 중요!!
            do {
                numbers_int.insert(stoi(temp));
            } while (next_permutation(temp.begin(), temp.end()));

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

    for (int number: numbers_int) {
        bool isPrime = true;
        if (number <= 1) continue;

        for(int i = 2; i < number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) answer++;
    }
    
    return answer;
}

예전에 STL을 쓰지 않고 combination을 구현하기 위해 꽤나 애먹었지만 algorithm 라이브러리 안에 있는 next_permutation이란 것을 써서 꽤나 간단해졌다.

첫번재 do while문에서는 string 안에서 x개의 숫자를 추리는 조합을 만들었고, 그 안에 있는 do while문에는 각 숫자별로 만들 수 있는 모든 조합을 추려서 integer로 바꿔 numbers_int라는 set에 넣어줬다.

set을 쓴 이유는 중복되는 숫자를 피하기 위해서!

여기서 중요한 것은 next_permutation은 현재 순서에서 바로 다음 순열을 가져오기 때문에 만약 모든 조합을 찾고 싶다면 한번 sort를 해줘야 한다!

다만 이 경우 nC1 1! + nC2 2! + ... nCn*n! = O(c^n)의 시간복잡도를 가졌고 redundancy가 너무 많다고 느껴졌다.

다른 풀이들을 보며 조금 더 나은 풀이로 개선할 수 있었다.

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

using namespace std;

int solution(string numbers) {
    int answer = 0;
    set<int> numbers_int;
    
    sort(numbers.begin(), numbers.end());

    do {
        for(int i = 1; i <= numbers.length(); i++) {
            numbers_int.insert(stoi(numbers.substr(0,i)));
        }
    } while (next_permutation(numbers.begin(), numbers.end()));
    

    for (int number: numbers_int) {
        cout << number << endl;
        bool isPrime = true;

        if (number <= 1) continue;

        for(int i = 2; i < number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) answer++;
    }

    return answer;
}

위와 같이 하면 단 do while문만 사용하면서 전체 string의 조합만 전부 추린다. 각 조합 별로 모든 substring들을 set 안에 넣어주기만 하면 되기 때문에 O(n * n!)의 시간복잡도를 가지게 되고 실제로 running time도 눈에 띄게 줄어들었다.

---

References

• c++ set STL https://blockdmask.tistory.com/79

• 다른 풀이 https://codingwell.tistory.com/32

• c++ next_permutation STL https://notepad96.tistory.com/39

• c++ next_permutation 을 사용해서 combination 찾기 https://notepad96.tistory.com/entry/C-조합Combination-구하기

---

만약 더 나은 풀이나 잘못된 로직이 있다면 댓글을 통해 알려주시면 감사하겠습니다 :)