[백준] 16943번 : 숫자 재배치 (C++)

16943번 : 숫자 재배치

---

문제)

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

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

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

 

 

풀이)

// 16943. 숫자 재배치
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
string a;
int b;
int n;
 
vector<char> vec;
vector<bool> visited;
 
int ans = -1;
 
void recur(int cur)
{
    // C는 0으로 시작하면 안된다. (가지치기)
    if (cur >= 1 && vec[0] == '0') return;
 
    // C가 완성되었다면 숫자로 바꿔보고,
    // 최댓값을 갱신한다.
    if (cur == n)
    {
        string temp = "";
        for (int i = 0; i < cur; i++)
        {
            temp += vec[i];
        }
 
        int t = stoi(temp);
 
        if (t != 0 && t < b) ans = max(ans, t);
        
        return;
    }
 
 
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == true) continue;
 
        visited[i] = true;
        vec[cur] = a[i];
        recur(cur + 1);
        visited[i] = false;
    }
}
 
int main()
{
    cin >> a >> b;
 
    n = a.length();
    vec.resize(n);
    visited.resize(n, false);
 
    recur(0);
 
    cout << ans;
 
    return 0;
}

---

출처 : https://www.acmicpc.net/problem/16943 

16943번: 숫자 재배치