[C++] 엘리스 알고리즘 코드 챌린지 7/8 : 목표량

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string str;
int n;
string res;
bool fin = false;
vector<int> a;
vector<bool> chk;

void dfs(int idx) {
    if (fin) {
        return;
    }
    if (idx == n) {
        if (res > str) {
            for (char c: res) {
                cout << c;
            }
            cout << '\n';
            fin = true;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!chk[i]) {
            chk[i] = true;
            res.replace(idx, 1, to_string(a[i]));
            dfs(idx + 1);
            if (fin) break;
            chk[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> str;
    res = str.substr();
    n = str.size();
    chk = vector<bool>(n);

    for (char c: str) {
        a.push_back(c - '0');
    }

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

    dfs(0);
}

분명 다른 더 좋은 방법이 있을 것 같은데 안 떠올라서 결국 그냥 백트래킹으로 풀었다. 당연히 시간 초과 날 줄 알았는데 이게 왜 되지..?? 암튼 여행 와있지만 숙소에서 노트북으로 11시 20분에 마무리ㅠㅠ!!

(추가) next_permutation을 쓰면 날먹으로 풀 수 있다고 한다.