[백준] 2529-부등호(C++)

문제링크:www.acmicpc.net/problem/2529

2529번: 부등호

 

algorithm 라이브러리에서 제공하는 순열 함수를 사용하여 해결했습니다.

 

k+1개의 수를 만든 다음 큰 수부터 작은 수순으로, 그리고 작은 수부터 큰 수순으로 차례대로 결과값이 될 수 있는지 확인해주면 결과를 도출했습니다.

 

처음에 재귀함수로 접근하려고 했는데 생각해보니 굳이 필요없을 것 같습니다. 

아래는 정답코드입니다.

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

int k;
vector <char> arr;
vector <int> val;
bool chk() {

	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == '<') {
			if (val[i] > val[i + 1])
				return false;
		}
		else {
			if (val[i] < val[i + 1])
				return false;
		}
	}
	return true;
}


int main() {

	cin >> k;
	for (int i = 0; i < k; i++) {
		char temp;
		cin >> temp;
		arr.push_back(temp);
	}
	for (int j = 0, i = 9; j < k + 1; j++,i--) 
		val.push_back(i);
	while (1) {
		if (chk() == true)
			break;
		prev_permutation(val.begin(), val.end());
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;

	val.clear();
	for (int i = 0; i < k + 1; i++)
		val.push_back(i);

	while (1) {
		if (chk() == true)
			break;

		next_permutation(val.begin(), val.end());
		
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;
	return 0;

}