알고리즘: 웨브바짐 문제 분해 - 1

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다.

먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE

입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자의 순서를 바꾸어 나타낼 수 있는 모든 경우의 수를 출력하라. 단, num의 각 자릿수의 숫자는 서로 다르다. (예: 123, 385, 9285, 2738은 가능하며, 2288, 1233은 불가능)

해설 : 먼저 int 형으로 입력받은 num의 각 자릿수의 숫자를 vector<int> vec에 순차적으로 삽입합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> logVec;
vector<int> vec;
vector<bool> usedVec;
 
void main(){
    int num;
    cin >> num;
    while (num > 0){
        vec.push_back(num % 10); //각 자릿수의 숫자를 추출하여 vec에 순차적으로 삽입
        usedVec.push_back(false);
        num /= 10;
    }
    sort(vec.begin(), vec.end()); //정렬함수 (각 원소를 오름차순으로 정렬)
}

18번째 라인까지 수행이 되면 vec에는 입력받은 수의 각 자릿수 숫자가 오름차순으로 저장되어 있게 됩니다.

다음으로, 반복문과 재귀문을 사용하여 vec의 첫 번째 원소부터 순차적으로 선택하여 vec의 숫자들을 모두 사용하면서 나타낼 수 있는 모든 수들을 출력해야 합니다.

int price(int idx){
    int size = vec.size();
    if (idx == size){
        int logSize = logVec.size();
        for (int i = 0; i < logSize;i++){
            cout << logVec[i];
        }
        cout << endl;
        return 1;
    }
    int cnt = 0;
    for (int i = 0; i < size; i++){
        if (usedVec[i])
            continue;
        logVec.push_back(vec[i]);
        usedVec[i] = true;
        cnt += price(idx + 1);
        usedVec[i] = false;
        logVec.pop_back();
    }
  return cnt;
}

price라는 함수를 정의하고 매개변수로 현재 채워넣을 자릿수 값인 idx를 받습니다. 만약, idx = 0이라면, 현재 가장 높은 자릿수의 숫자를 선택할 순서입니다. 라인 12과 같이 최대 자릿수이자 vec의 원소 개수인 size만큼 반복문을 수행하면서 현재 선택될 수 있는 숫자들을 찾는 과정을 수행하게 됩니다. 라인 13에서 사용되는 usedVec은 vec의 각 자릿수의 숫자가 이미 사용된 경우 true 그렇지 않은 경우 false를 가지게 됩니다. 따라서, 라인 13과 같이 반복문의 현재 vec의 값이 이미 사용중이라면 다음 값을 검사하게 됩니다. 만약 사용되지 않은 경우라면 해당 값을 선택하고 라인 15와 같이 출력을 위해 해당 값 (vec[i])을 logVec에 삽입합니다. 현재 vec 값이 사용되었다는 것을 저장하기 위해 라인 16과 같이 usedVec[i]를 true로 저장합니다. 그리고 idx 번째 자릿수를 방금 선택하였으므로, idx+1번째 자릿수를 선택하기 위해 price 함수에 idx +1를 매개변수로 하여 재귀적으로 호출을 시도합니다. price 함수의 반환 값은 현재까지 선택된 값들로 인해 나타날 수 있는 모든  경우의 수가 됩니다. 이와 같은 반복문을 통해 현재 자릿수에 가능한 모든 값들을 적용해나가면서 만약 모든 자리의 수를 가득 채웠다면, 라인 3-10과 같이 logVec에 보관했던 값들을 순차적으로 출력하여 현재 선택된 값을 나타냅니다. 또한, 1을 반환하여 나열이 가능한 경우라는 것을 표시합니다. 이러한 경우들을 모두 검사하고 출력함으로써 num의 모든 가능한 나열을 구할 수 있게 됩니다.