2529..md

description	오름차순 한 번, 내림차순 한 번!

2529. 부등호

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

vector<char> opr;
vector<int> ans_max;
vector<int> ans_min;
bool flag = false;

vector<int> concat(vector<int> &v1, vector<int> &v2)
{
    vector<int> new_v = {v1};
    new_v.insert(new_v.end(), v2.begin(), v2.end());
    return new_v;
}

bool check(vector<int> v)
{
    for (int i=0; i<opr.size(); i++)
    {
        if (opr[i] == '<')
        {
            if (v[i] > v[i+1])
            {
                return false;
            }
        }
        else // opr[i] == '>'
        {
            if (v[i] < v[i+1])
            {
                return false;
            }
        }
    }
    return true;
}

void permutation(vector<int> &p, vector<int> &v ,int k, bool isAscending) // p가 안빈거, v가 빈거
{
    if (k==0)
    {
        // check 돌려서 true이면 ans에 삽입
        if (check(v)==true)
        {
            if (isAscending)
            {
                ans_min = v;
            }
            else
            {
                ans_max = v;
            }
            flag = true;
            return;
        }
    }
    else
    {
        for (int i=0; i<p.size() && flag == false; i++)
        {
            v.push_back(p[i]);
            vector<int> sub_p1 = vector<int>(p.begin(), p.begin()+i);
            vector<int> sub_p2 = vector<int>(p.begin()+i+1, p.end());
            vector<int> sub_p = concat(sub_p1, sub_p2);
            permutation(sub_p, v, k-1, isAscending);
            v.pop_back();
        }
    }
}

int main()
{
    int n; // 부등호 개수
    cin >> n;
    
    vector<int> visited_up; // index 0~9까지 안빈거
    for (int i=0; i<=9; i++)
    {
        visited_up.push_back(i);
    }

    vector<int> visited_down;
    for (int i=9; i>=0; i--)
    {
        visited_down.push_back(i);
    }
    
    vector<int> permu; // Permutation을 담을 배열 - 빈거
    
    for (int i=0; i<n; i++)
    {
        char temp;
        cin >> temp;
        opr.push_back(temp);
    }
    
    permutation(visited_up, permu, n+1, true);
    flag = false; // 다시 돌리기 전에 초기화
    permutation(visited_down, permu, n+1, false);
    
    for (int i : ans_max)
    {
        cout << i;
    }
    cout << "\n";
    for (int i : ans_min)
    {
        cout << i;
    }
    cout << "\n";
    
    return 0;
}