[C++] Samsung SW Expert Academy 1244. [S/W 문제해결 응용] 2일차 - 최대 상금

/*

When I made 'check' as Map STL, it failed because it's too slow.
After I changed check to bool array, it got much faster.

It means that Map STL is sooooooooooo much slow.






*/

#include <iostream>
#include <string>

using namespace std;

bool check[100][999999]; //최대 교환 횟수를 100으로 가정함.
int max_num;

void calc(string num, int len, int change) {
    if(change==0) {   
        int result = stoi(num);
        max_num = max(max_num,result);

    } else {
        for(int i=0;i<len;i++) {
            for(int j=i+1;j<len;j++) {
                if(num[i] > num[j]) continue;
                char temp = num[i];
                num[i] = num[j];
                num[j] = temp;

                if(check[change-1][stoi(num)]) {
                    temp = num[i];
                    num[i] = num[j];
                    num[j] = temp;
                    continue;
                } else {
                    check[change-1][stoi(num)] = true;
                    calc(num,len,change-1);
               
                    temp = num[i];
                    num[i] = num[j];
                    num[j] = temp;
                }
            }
        }   
    }
}

int main() {
    int N;
    cin >> N;
   
    for (int i=1;i<=N;i++) {
    string num;
        int change;
        cin >> num;
        cin >> change;
        int len = num.size(); 
       
        max_num = 0;

calc(num,len,change);
       
       cout << "#" << i << " " << max_num << endl;
    }
   
return 0;
}