🍗2529번. 부등호, 10팩토리얼 : 시간 복잡도. 362만. -> 완탐이 가능한 문제. _ 전체를 한번에 처리하자.

단위별로 처리하는 것보다, 전체를 한번에 처리하는 것이 가능하다면, 한번에 처리하자.

• 단위별로 끊어서 처리하기 보다는 , 모든 입력 예제에서
  공통적으로 처리가 가능하다면, 한번에 처리하자
  --> 시간복잡도 효율도 좋고, 나도 편하게 계산이 가능하다.

string도 max ,min 처리가 가능함.

😉풀이 전략에 대해 다른 방법도 있는지 생각을 해보자. 더 효율적인 거라고 생각한 걸로 접근하자.

• 맨 처음 문제를 접했을 때

  : 부등호 2개에 맞는 숫자를 부등호 하나하나씩 비교하면서 진행하려는 프로세스를 만들려고 했음. 부등호에 옳지 않으면, 다시 돌아가서 변경하는 로직.
  but 한번에 숫자 취합하는 방법으로 변경함.
  만약 부등호가 최대인 10개? 가 나오면 10! : 360만 이므로
  완탐이 가능한 시간 복잡도 이다.
  조합완료된 숫자 통째로 가지고 와서 비교를 해도 됨.
  그리고 이것이 보다 쉽게 접근 가능한 방법.
  

시간복잡도

: 10! 의 시간 복잡도는 360만 임.
-> 완전 탐색으로 풀어도 ㄱㅊ!

생각해볼점.

1) 부등호 체크 하는 함수를 매번 확인하는 방법.
2) 문자열에 다 넣어버린 다음에 , 부등호 체크를 한번에 하는 방법
-> 2번이 훨씬 효율적임. 함수 호출을 줄일 수 있기 때문임.

코드

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

// 부등호 최대 9개만 사용가능함. 
// 부등호 연산한 값들 총 10개가 최대임.

// 백트래킹 반복문에서 다음 인덱스를 지칭하기 위한.
// 변수임. 
bool check[10];

int n;

vector<string>vv;

// 부등호 컨테이너를 알아야 함. 
bool Result(vector<char>&op , string & word)
{
	for (int i = 0; i < word.size() - 1; ++i)
	{
		if (op[i] == '<')
		{
			if (word[i] > word[i + 1])
			{
				return false;
			}

		}
		else if(op[i] == '>')
		{
			if (word[i] < word[i + 1])
			{
				return false;
			}
		}

	}

	return true;
}


// 숫자 중에서 몇번째 인덱스에 위치한 것을 
//처리할 것인지
// 예를 들어서 < > 이라면 숫자가 3개는 와야 함. 
void backTracking( int index ,string word , vector<char>&op)
{
	// 부등호가 2개일 때는 3개에서 스톱!
	if (index >= n + 1)
	{
		// string에다가 문자열 담아가지고 
		// 한번에 체킹 함수에다가 던져가지고 확인하도록 하자.
		if (Result(op, word))
		{
			//전역 벡터에다가 저장해놓음. 
			vv.push_back(word);
			
			// 출력 확인용 
			//cout << word << endl;
		}
		
		return;
	}

	// 0에서 9까지의 숫자가 들어 갈수 있음. 
	for (int i = 0; i <= 9; ++i)
	{
		if (check[i])
			continue;

		check[i] = true;
		string temp = to_string(i);

		backTracking(index + 1 , word + temp, op);


		check[i] = false;

	}


}


int main() 
{
	
	cin >> n;

	vector<char>v(n);

	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}

	backTracking(0, "", v);

	cout << *max_element(vv.begin(), vv.end()) << endl;
	cout << *min_element(vv.begin(), vv.end());
}