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

2529번: 부등호

---

문제

백준문제이미지

---

풀이

K는 0 ~ 9까지의 수 즉 10개이다.

부등호를 만족하는 가장 큰 수를 만들기 위해서는 0~9중 가장 큰 수를 순서대로 넣으면 되고

부등호를 만족하는 가장 작은 수를 만들기 위해서는 0~9중 가장 작은 수를 순서대로 넣으면 된다.

 

처음 큰 수와 작은 수를 저장한 배열에 큰 수는 9부터 작은 수는 0부터 들어가므로

가장 큰 수는 prev_permutation을 가장 작은 수는 next_permutation을 사용하여

입력한 부등호에 맞는 수를 구해주면 된다.

---

문제점

---

코드

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

bool check(vector<int> &perm, vector<char> &a)
{
    for (int i = 0; i < a.size(); ++i)
    {
        if (a[i] == '>' && perm[i] < perm[i + 1])
        {
            return false;
        }
        if (a[i] == '<' && perm[i] > perm[i + 1])
        {
            return false;
        }
    }
    return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int k;
    cin >> k;

    vector<char> a(k);
    for (int i = 0; i < k; ++i)
    {
        cin >> a[i];
    }

    vector<int> small(k + 1);
    vector<int> big(k + 1);
    for (int i = 0; i <= k; ++i)
    {
        small[i] = i;
        big[i] = 9 - i;
    }

    // 가장 작은 값
    do
    {
        if (check(small, a))
        {
            break;
        }
    } while (next_permutation(small.begin(), small.end()));

    // 가장 큰 값
    do
    {
        if (check(big, a))
        {
            break;
        }
    } while (prev_permutation(big.begin(), big.end()));
    
    for (int i = 0; i < big.size(); ++i)
    {
        cout << big[i];
    }
    cout << "\n";
    for (int i = 0; i < small.size(); ++i)
    {
        cout << small[i];
    }
    cout << "\n";

    return 0;
}

---

결과

결과 이미지

---

pyo7410/Study