백준_2529_부등호

재귀를 이용해서 풀었다.

재귀 함수로 정수 문자열을 만들고, 정수 문자열의 길이가 k+1 이 되면, 이 문자열이 부등호를 만족하는지 check 함수로 확인했다.

만족하면, 정답 후보에 저장했다.

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

int k;
vector<char> v;
bool visited[MAX];
vector<string> ans;

bool check(string num_str) { // 부등호 만족하는지 확인
	for (int i = 0; i < k; i++) {
		if (v[i] == '<') {
			if (num_str[i] > num_str[i + 1]) return false;
		}
		else if (v[i] == '>') {
			if (num_str[i] < num_str[i + 1]) return false;
		}
	}
	return true;
}

void solve(string num_str, int cnt) { // 재귀
	if (cnt == k + 1) {
		if (check(num_str)) {
			ans.push_back(num_str);
		}
		return;
	}
	for (int i = 0; i < 10; i++) {
		if (!visited[i]) {
			visited[i] = true; // 그 숫자를 사용한 적이 없다면 사용
			solve(num_str + to_string(i), cnt + 1);
			visited[i] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	char c;
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> c;
		v.push_back(c);
	}
	solve("", 0);
	auto min_max = minmax_element(ans.begin(), ans.end());
	cout << *min_max.second << '\n';
	cout << *min_max.first << '\n';
	return 0;
}