16943 숫자 재배치

일단 아닌 경우를 전부 걸러 보았다.

 

1. a의 길이가 b의 길이보다 긴 경우 -> 이건 절대 네버 불가

 

2. b의 길이가 a의 길이보다 긴 경우 -> 무조건 된다 a를 가장 큰 수로 만들어주자

 

3. a와 b의 길이가 같은 경우 -> a의 순서를 섞으면서 조건에 맞는지 고민하면 된다......

 

3번의 경우가 되었을 때 어떻게 할지 고민하다가 처음에는 a의 counting 배열을 만든 다음 뒤에서부터 b랑 ㅣㅂ교하며 읽으면 안될까? 싶었는데 

 

a : 3412 b: 3000인 경우 a가 처음 3을 선택할꺼고 b가 0임을 확인한 이상 돌이킬 수 없는 강을 건너게 되므로 패스했다.

 

다음으로 그냥 a의 순열을 다 만든 다음 b랑 비교해서 작은 걸 선택하면 되겠다 싶었다.

 

그래서 전에 만든 순ㄴ열코드 들고와서 이리저리 만들었는데 틀렸넹ㅎㅎ

 

지금 글 적으면서 생각난건데 뭔가 0 때문에 문제가 생긴게 아닐까 싶다.. 아님 뭐가 문제지

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int v[10];
bool visited[10];
vector<int> selects;
int ans = 0;
int n, m;

void	comb(int depth)
{
    if (depth == n)
    {
        string str;

        for (int i = 0; i < n; i++)
        {
            str += to_string(selects[i]);
        }
        
        int num = stoi(str);
        if (ans < num && num <= m)
            ans = num;

        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (visited[i])
            continue;

        visited[i] = true;
        selects.push_back(v[i]);
        comb(depth + 1);
        visited[i] = false;
        selects.pop_back();
    }
}


int     main()
{
    string a, b;
    cin >> a >> b;

    if (a.size() > b.size())
    {
        printf("-1\n");
        return 0;
    }

    if (a.size() < b.size())
    {
        sort(all(a), greater<char>());
        cout << a;
        return 0;
    }

    n = a.size();
    m = stoi(b);

    for (int i = 0; i < a.size(); i++)
    {
        v[i] = a[i] - '0';
    }

    comb(0);

    if (ans == 0)
        printf("-1\n");
    else
        printf("%d\n", ans);

    return 0;
}

 

 

---

떼이잉~ 0으로 시작하면 안 된다는게 0012 말고 12로 적으라는 뜻인 줄 알았는데 0으로 시작하지 말라는 뜻이었다.

 

보통 0으로 시작할 수 없다고 적어놓으면 0으로 시작하지 말라는 거고 0을 적으면 안 되는 건 따로 명시를 해준다고 한다. 알아두겠서 

 

해결은 간단했다. 0으로 시작하면 패스하게 했음

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int v[10];
bool visited[10];
vector<int> selects;
int ans = 0;
int n, m;

void	comb(int depth)
{
    if (depth == n)
    {
        string str;

        if (selects[0] == 0)
            return;

        for (int i = 0; i < n; i++)
            str += to_string(selects[i]);
        
        int num = stoi(str);

        if (ans < num && num <= m)
            ans = num;

        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (visited[i])
            continue;

        visited[i] = true;
        selects.push_back(v[i]);
        comb(depth + 1);
        visited[i] = false;
        selects.pop_back();
    }
}


int     main()
{
    string a, b;
    cin >> a >> b;

    if (a.size() > b.size())
    {
        printf("-1\n");
        return 0;
    }

    if (a.size() < b.size())
    {
        sort(all(a), greater<char>());
        cout << a;
        return 0;
    }

    n = a.size();
    m = stoi(b);

    for (int i = 0; i < a.size(); i++)
    {
        v[i] = a[i] - '0';
    }

    comb(0);

    if (ans == 0)
        printf("-1\n");
    else
        printf("%d\n", ans);

    return 0;
}