[백준/C++] 부등호

부등호

풀이

문자열에 완성된 숫자들을 집어넣고 부등호조건을 만족하는지를 검사하여 MAX와 MIN을 업데이트 시켜주는 코드다. 아직 이때 백트레킹을 잘 못하던 시기였던 것 같다. 문자열을 만드는 과정에서 부등호 조건을 만족시키지 못한다면 바로 반환하도록 하는 것이 더 좋아보인다. 귀찮으므로 생략

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

int k;
string MAX = "0", MIN = "9876543211";
bool visit[10] = {false};
string list ="0123456789";
string ans;
string compare;

bool chk()
{
	for(int i = 0; i < k; ++i) {
		if(compare[i] == '>' && ans[i] < ans[i+1])
			return false;
		if(compare[i] == '<' && ans[i] > ans[i+1])
			return false;
	}
	return true;
}

void permutation(int cnt)
{
	if(cnt == k + 1) {
		if(!chk()) return;
		if(stoll(ans) > stoll(MAX)) MAX = ans;
		if(stoll(ans) < stoll(MIN)) MIN = ans;
		return;
	}

	for(int i = 0; i < 10; ++i) {
		if(visit[i]) continue;
		visit[i] = true;
		ans.push_back(list[i]);
		permutation(cnt + 1);
		visit[i] = false;
		ans.pop_back();
	}
}

int main()
{
	cin >> k;
	for(int i = 0; i < k; ++i) {
		char tmp;
		cin >> tmp;
		compare.push_back(tmp);
	}

	permutation(0);
	
	cout << MAX << "\n";
	cout << MIN;

	return 0;
}