2529 - 부등호

문제 :

https://www.acmicpc.net/problem/2529

2529번: 부등호

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

int K;
constexpr int MAX = 9;
constexpr int NUM_LENGTH_MAX = 10;
array<char, MAX + 1> inequality{ 0 };
array<int, NUM_LENGTH_MAX + 1> is_visited{ 0 };
vector<string> ans;

bool is_correct(string& temp)
{
	bool ret = true;
	for (int i = 0; i < K; i++) {
		if (inequality[i] == '<') {
			if (temp[i] >= temp[i + 1]) {
				return ret = false;
			}
		}
		else if (inequality[i] == '>') {
			if (temp[i] <= temp[i + 1]) {
				return ret = false;
			}
		}
	}

	return ret;
}

void Run(const int start_idx, const int depth, string temp)
{
	if (is_visited[start_idx]) {
		return;
	}

	is_visited[start_idx] = true;
	temp += to_string(start_idx);
	if (K == depth) {
		if (is_correct(temp)) {
			ans.push_back(temp);
		}

		is_visited[start_idx] = false;
		return;
	}

	for (int i = 0; i <= 9; i++) {
		Run(i, depth + 1, temp);
	}

	is_visited[start_idx] = false;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> inequality[i];
	}

	for (int i = 0; i <= 9; i++) {
		Run(i, 0, "");
		memset(&is_visited, 0x00, sizeof(is_visited));
	}

	sort(ans.begin(), ans.end());

	cout << ans[ans.size() - 1] << '\n';
	cout << ans[0] << '\n';
	return 0;
}

• 브루트포스 방법을 이용해 풀 수 있는 문제였습니다.
• 재귀함수를 이용했습니다. 트리의 MAX 깊이가 10 이고, 모든 경우가 깊이 10까지 들어가지 않기 때문에 시간초과가 나지 않을 것이라고 생각했습니다.
• 하지만 생각보다 elapsed time이 컸습니다. 방법을 수정해도 좋을것 같습니다.