[BOJ] 2529. 부등호

https://www.acmicpc.net/problem/2529

2529번: 부등호

주어지는 부등호에 맞는 순열 중 최솟값과 최댓값을 찾는 문제이다.

각 부등호의 앞뒤 숫자만 맞으면 된다.

 

이 문제는 permutation을 써서 쉽게 구할 수 있다.

최댓값은 9876543210부터 시작하여 이전 순열을 구해서 찾아주고

최솟값은 0123456789부터 시작하여 다음 순열을 구해서 매번 부등호를 만족하는지 검사해주면 된다.

식을 만족하면 바로 출력해주고 break 해줘서 더 이상 다음 순열을 구하지 않는다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
char arr[9];
int n;
vector<int> num;
 
bool check() {
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (arr[i] == '<') {
            if (num[i] > num[i + 1]) {
                ok = false;
                break;
            }
        }
        else {
            if (num[i] < num[i + 1]) {
                ok = false;
                break;
            }
        }
    }
 
    return ok;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
 
    //9부터 0까지 넣는다.
    for (int i = 9; i >= 0; i--) {
        num.push_back(i);
    }
 
 
    //최댓값을 구하기 위해 9876543210부터 이전 순열을 구한다.
    do {
        
        //식을 만족하면 print하고 break
        if (check()) {
            for (int i = 0; i <= n; i++) {
                cout << num[i];
            }
            cout << '\n';
            break;
        }
    } while (prev_permutation(num.begin(), num.end()));
 
 
    //벡터를 정리해준뒤에 0부터 9로 다시 채워넣는다.
    num.clear();
    for (int i = 0; i < 10; i++) {
        num.push_back(i);
    }
 
    //최솟값을 구하기 위해 0123456789부터 다음순열을 구한다.
    do {
 
        if (check()) {
            for (int i = 0; i <= n; i++) {
                cout << num[i];
            }
            cout << '\n';
            break;
        }
    } while (next_permutation(num.begin(), num.end()));
 
    
 
    return 0;
}