[BOJ] 2529번_부등호_브루트포스 (C++)

[문제]

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

입력받은 부등호에 맞게 0~9까지의 숫자를 중복없이 배치한 후 부등호를 제외한 수를 붙여 하나의 정수를 만들었을 때, 가장 큰 정수와 가장 작은 정수를 구하는 문제이다.

[사용 알고리즘]

브루트포스 알고리즘

[풀이 핵심]

• 0~9의 숫자로 이루어진 정수이며, 중복되지 않아야 하므로 최대 10자리 숫자밖에 안된다. 따라서 완전 탐색을 이용해도 시간초과가 나지 않는다.
• 0~9의 숫자를 넣어보며 모두 확인하되, check함수를 통해 확인한 부등호가 거짓이면 넘어가고 참일때만 진행한다.
• 그렇게 만들어진 수를 전부 vector에 저장해두고 algorithm 헤더의 sort함수를 통해 정렬한 후 맨 뒤 값(최대 값)과 맨 앞 값(최소 값)을 출력한다.

[코드]

//boj2529번_부등호_브루트 포스

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int K;
vector<char> oper;
vector<string> result;
bool num_check[10];

bool check(int x, int y, char op) {
	if (op == '<') {
		if (x < y) {
			return true;
		}
	}
	else if (op == '>') {
		if (x > y) {
			return true;
		}
	}
	return false;
}

void solve(int index, string num) {
	if (index == K + 1) {
		result.push_back(num);
		return;
	}

	for (int i = 0; i < 10; i++) {
		if (!num_check[i]) {
			if (index == 0 || check(num[index - 1] - '0', i, oper[index - 1])) {
				num_check[i] = true;
				solve(index + 1, num + to_string(i));
				num_check[i] = false;
			}
		}
	}
}

int main() {
	cin >> K;

	for (int i = 0; i < K; i++) {
		char op;
		cin >> op;
		oper.push_back(op);
	}

	solve(0, "");

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

	cout << result[result.size() - 1] << '\n' << result[0];

}