백준(BOJ) 2629 부등호 *

이 문제는 분류에 위상정렬로 되어있지만 위상정렬로 구현하기보다는
백트래킹을 이용하는 방법이 더 좋은 방법이라고 생각했다.

입력을 받는부분에서 실수를 해서 애를 좀 먹었다.
다른 분들의 블로그를 보았는데 깔끔하게 해결한 코드가 보이지는 않았다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <utility>
#include <functional>
#define MAX 40005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

int n,cnt=0,mx[15],mi[15];
vector<char> op;

void backtrack(int cur,int arr[])
{
	if (cur == 0)
		return;
	if (op[cur-1] == '>' && arr[cur - 1] > arr[cur])
		return;
	if (op[cur-1] == '<' && arr[cur - 1] < arr[cur])
		return;
	// 부등호가 성립하면 종료시킨다.
	swap(arr[cur - 1], arr[cur]);
	// 부등호가 성립하지 않는다면 이전의 위치와 바꿔준다
	backtrack(cur - 1, arr);
	// 재귀를 이용하여 이전의 위치로 이동한다.
}

int main()
{
	scanf("%d", &n);
	while (cnt!=n)
	{
		char tmp;
		scanf("%c", &tmp);
		if (tmp == '<' || tmp == '>')
		{
			cnt++;
			op.push_back(tmp);
		}
	}
	// op 벡터에 부등호를 입력받아온다.

	mx[0]=9;
	mi[0]=0;

	for (int i = 1; i <= n; i++)
	{
		mx[i] = 9 - i;
		backtrack(i,mx);
		mi[i] = i;
		backtrack(i,mi);
	}
	// 최대 값에는 내림차순으로, 최소 값에는 오름차순으로 배열에 추가한다.
	// 이후 백트래킹을 이용하여 해결한다.

	for (int i = 0; i < n+1; i++)
		printf("%d", mx[i]);
	printf("\n");
	for (int i = 0; i < n+1; i++)
		printf("%d", mi[i]);
	return 0;
}