[C++] 백준 2992번 크면서 작은 수

https://www.acmicpc.net/problem/2992

풀이 1

백트래킹을 이용하는 방법이다.
정수 x를 구성하는 숫자들을 오름차순으로 정렬하고, 그 숫자들로 만들 수 있는 순열을 오름차순으로 생성하면서 x보다 큰 최소의 순열을 출력한다.

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

string x;
string ans;
vector<char> num;
vector<bool> is_used;
bool has_answer;

void backtracking(int cnt) {
    if(cnt == x.size()) {
        if(ans > x) {
            has_answer = true;
            cout << ans;
        }
        return;
    }
    
    for(int i=0; i<x.size(); i++) {
        if(is_used[i]) continue;
        ans += num[i];
        is_used[i] = true;
        
        backtracking(cnt+1);
        
        if(has_answer) return;
        
        ans.pop_back();
        is_used[i] = false;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> x;
    
    for(char c : x) num.push_back(c);
    sort(num.begin(), num.end());

    is_used.resize(x.size(), false);
    
    backtracking(0);
    
    if(!has_answer) cout << 0;
    
    return 0;
}

풀이 2

정수 x를 뒤에서부터 탐색하면서 감소하는 지점을 찾는다. 정수 x를 구성하는 수 중 그 지점의 수보다 큰 것이 있으면 둘을 교환한다. 그 지점 뒤부터 오름차순으로 정렬한다.

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

bool solution(string &s) {
    int n = s.size();

    int i = n - 1;
    while (i > 0 && s[i - 1] >= s[i]) i--;

    if (i == 0) return false;
    
    int j = n - 1;
    while (s[j] <= s[i - 1]) j--;

    swap(s[i - 1], s[j]);

    reverse(s.begin() + i, s.end());
    
    return true;
}

int main() {
    string x;
    cin >> x;
    
    if (solution(x)) cout << x;
    else cout << 0;

    return 0;
}

풀이 3

C++의 next_permutation()을 이용하면 쉽게 해결할 수 있다.

next_permutation()

• 현재 배열을 다음 순열로 직접 변경
• 다음 순열이 존재하면 true, 그렇지 않으면 false 반환

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

int main() {
    string x;
    cin >> x;
    
    if (next_permutation(x.begin(), x.end())) cout << x;  
    else cout << 0;

    return 0;
}

참고

prev_permutation()은 next_permutation()과 반대로 이전 순열을 구한다.