[C++ / 백준 2529번] 부등호

 

 

재귀, 백트래킹 을 이용하여 풀이했다.

next_permutation을 사용하면 더 빨리 풀 수 있을 것 같다. 시간 복잡도가 다르기 때문에. 

범위는 항상 조심하자.

 

 

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

int k[12];
long long MinNum = 9999999999;
long long MaxNum = -1;

vector <int> PermuVec;

int visited[10] = { false };

int N;

bool checkCondition(vector<int> inputVec)
{
    for (int i = 0; i < N; i++)
    {
        if (k[i] == 0 && PermuVec[i] > PermuVec[i+1])
        {
            return false;
        }
        if (k[i] == 1 && PermuVec[i] < PermuVec[i + 1])
        {
            return false;
        }
    }

    return true;
}


void recur(int depth)
{
    if (depth == N + 1)
    {
        /*
        for (auto i : PermuVec)
        {
            cout << i << " ";
        }
        cout << '\n';
        */

        long long tmp = 0;

        for (auto i : PermuVec)
        {
            tmp = tmp*10 + i;
            
        }


        if (checkCondition(PermuVec))
        {
            MaxNum = max(MaxNum, tmp);
            
            MinNum = min(MinNum, tmp);
        }


        return;
    }

    for (int i = 0; i <= 9; i++)
    {
        if(!visited[i])
        { 
            PermuVec.push_back(i);
            visited[i] = true;
           
            recur(depth + 1);
            
            PermuVec.pop_back();
            visited[i] = false;
        }
    }


}

int main() 
{
    
    cin >> N;

    char input;

    for (int i = 0; i < N; i++)
    {
        cin >> input;

        if (input == '<')
        {
            k[i] = 0;
        }
        else
        {
            k[i] = 1;
        }
    }


    recur(0);

    if (to_string(MaxNum).length() != N + 1) cout << "0" << MaxNum;
    else cout << MaxNum;

    cout << '\n';

    if (to_string(MinNum).length() != N + 1) cout << "0" << MinNum;
    else cout << MinNum;



    return 0;
}