BOJ : 2529 부등호

---

[BOJ 2529(S2) 리뷰]

오랜만에 백트래킹 카테고리에서 문제를 풀었다. 실버문제라 그런지 쉽게 구현을 떠올릴 수 있었다.

전형적인 백트래킹 방법을 통해서 부등호 조건에 맞지 않는 경우 가지치기를 하면 된다.

다만 출력할때 021 이런식으로 맨 앞자리에 0이 오는경우가 있으므로 문자열로 출력해야 한다.

이때 어떻게 할까 고민을하다 그냥 string객체에 max,min함수를 써봤는데 잘 동작했다.

 

---

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

char ans[10];
string ansmin("987654321");
string ansmax("0");
vector <char> sign;
bool isUsed[10];
int k;

void go(int n)
{
	if (n > 1)
	{
		char s = sign[n-2];
		if (s == '>')
		{
			if (ans[n - 2] < ans[n-1])
				return;
		}
		else if (s == '<')
		{
			if (ans[n - 2] > ans[n-1])
				return;
		}
	}
	if (n == k + 1)
	{
		ans[k + 1] = '\0';
		string s(ans);
		ansmax=max(s, ansmax);
		ansmin=min(s, ansmin);
		return;
	}


	for (char c = '0'; c <= '9'; c++)
	{
		if (isUsed[c - '0']) continue;
		ans[n] = c;
		isUsed[c - '0'] = 1;
		go(n + 1);
		isUsed[c - '0'] = 0;
	}

}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> k;
	for (int i=0;i<k;i++)
	{
		char c;
		cin >> c;
		sign.push_back(c);
	}
	
	go(0);

	cout << ansmax << '\n' << ansmin;
	
}