[BOJ] 2529번 부등호

풀이 소요시간 : 깜빡하고 측정 안함(?)

풀이 소요시간을 측정하지 않은 이유는 꽤 오랜만에 푼 문제이기 때문이다.
중간고사 기간 2주 정도 코딩테스트 문제를 풀지 않아서 머리가 굳었다.
다시 적응하는 차원에서 널널하게 잡고 풀었다.

접근방식

숫자 하나를 선택할 때 마다 부등호 체크를 해야 하지 않을까..?
순서 쌍을 다 구한다음에 수식 체크를 하는건 너무 일차원적인 생각인데..
시간 초과가 나는거 아닌가..?

라는 뒤틀린 고민으로 시간을 소모했다.
처음 생각한 단순한 방식이 정답이였다.

전체 코드

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

int N;
char Map[9];
int Visit[10];

vector<int> Vector;
vector<string> Result;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Map[i];
	}
}

// 부등호 조건 만족 확인
bool Check() {
	for (int i = 0; i < N; i++) {
		if (Map[i] == '<') {
			if (Vector[i] >= Vector[i + 1]) return false;
		} 
		else if (Map[i] == '>') {
			if (Vector[i] <= Vector[i + 1]) return false;
		}
	}
	return true;
}

// 결과 문자열 생성
void Make_Result() {
	string str = "";
	for (int i = 0; i < Vector.size(); i++) {
		str += to_string(Vector[i]);
	}
	Result.push_back(str);
}


void Dfs(int count) {

	if (count == N + 1) {
		if (Check() == true) {
			Make_Result();
		}
		return;
	}

	// N + 1 개의 숫자 select
	for (int i = 0; i <= 9; i++) {
		if (Visit[i] == 0) {
			Visit[i] = 1;
			Vector.push_back(i);

			Dfs(count + 1);
			//재귀 후 귀환

			Visit[i] = 0;
			Vector.pop_back();
		}
	}

}


int main() {
	Input();
	Dfs(0);
	sort(Result.begin(), Result.end());
	cout << Result[Result.size() - 1] << '\n';
	cout << Result[0] << '\n';
}

전체 코드(리팩토링 - 백트래킹 간략화)

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

int N;
char Map[9];
int Visit[10];

vector<int> Vector;
vector<string> Result;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Map[i];
	}
}

// 부등호 조건 만족 확인
bool Check(string str) {
	for (int i = 0; i < N; i++) {
		if (Map[i] == '<') {
			if (str[i] >= str[i + 1]) return false;
		} 
		else if (Map[i] == '>') {
			if (str[i] <= str[i + 1]) return false;
		}
	}
	return true;
}

void Dfs(int count, string str) {

	if (count == N + 1) {
		if (Check(str) == true) {
			Result.push_back(str);
		}
		return;
	}

	// N + 1 개의 숫자 select
	for (int i = 0; i <= 9; i++) {

		if (Visit[i] == 1) continue;

		Visit[i] = 1;
		Dfs(count + 1, str + to_string(i));
		// 자동 push, pop 이 구현된 셈이다.
		Visit[i] = 0;

	}

}


int main() {
	Input();
	Dfs(0, "");
	sort(Result.begin(), Result.end());
	cout << Result[Result.size() - 1] << '\n';
	cout << Result[0] << '\n';
}