백준 16943번 숫자 재배치 c++ 풀이

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

제한

• 1 ≤ A, B < 109

예제 입력 1 복사

1234 3456

예제 출력 1 복사

3421

예제 입력 2 복사

1000 5

예제 출력 2 복사

-1

예제 입력 3 복사

789 123

예제 출력 3 복사

-1

 

 

순열 문제

 

주의

next_permutation은 오름차순으로 정렬되어 있어야 제대로 사용 가능하다.

prev_permuation은 조합을 구할 때 주로 사용된다. 예) temp 벡터에 1,1,00을 넣으면 1인 경우만 구해서 2개의 조합을 구하는 것이 가능

 

 

#include <bits/stdc++.h>

using namespace std;

vector<char> v;

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

    string a;
    int b;
    cin >> a >> b;

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

    int maxAns = 0;

    do {

        int number = stoi(a);

        if (a[0] == '0') continue;

        if (number < b) {
            maxAns = number;
        }

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

    if (maxAns != 0) {
        cout << maxAns << "\n";
    } else {
        cout << -1 << "\n";
    }


}