백준_2529_부등호

📍문제: https://www.acmicpc.net/problem/2529

2529번: 부등호

 

📍알고리즘: 브루트포스 - 순열 (백트래킹(재귀)으로 풀 수 있음. → 속도 향상 가능)

 

📍아이디어: 부등호에 따른 숫자들의 순서만 정해지면, 실제로 각 숫자들이 어떤 숫자인지는 상관 없이, 그 순서에 맞게 고르면 부등호를 무조건 만족한다. 따라서, 최대수와 최소수를 구하는 문제이므로, 각각 987··· / 123··· 부터 시작해서 부등호의 순서를 정한다.

 

📍시간복잡도: (k+1)! * O(k)

👉이유: 부등호에 따른 순서를 정하는 데에 (k+1)! 소요, 순서에 맞게 permutation 함수로 다음 순열을 고르는 데에 O(n) 소요.

 

📍STL: next_permutation(v.begin(), v.end()) 과 prev_permutation(v.begin(), v.end())

👉함수의 시간복잡도는 O(n)이다. 아래 링크를 참고하자.

https://velog.io/@polynomeer/%EC%88%9C%EC%97%B4Permutation

순열(Permutation)

 

📍코드:

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

using namespace std;

int N; // 부등호 개수
char sign[9];

bool checkSign(vector<int> &perm) {
	for (int i = 0; i < N; i++) {
		if (sign[i] == '<') {
			if (perm[i] > perm[i + 1]) return false;
		}
		if (sign[i] == '>') {
			if (perm[i] < perm[i + 1]) return false;
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> sign[i];
	}

	vector<int> small(N + 1);
	vector<int> big(N + 1);

	for (int i = 0; i <= N; i++) {
		small[i] = i;
		big[i] = 9 - i;
	}

	do {
		if (checkSign(small)) {
			break;
		}
	} while (next_permutation(small.begin(), small.end()));

	do {
		if (checkSign(big)) {
			break;
		}
	} while (prev_permutation(big.begin(), big.end()));

	for (int i = 0; i < N + 1; i++) {
		cout << big[i];
	}
	cout << '\n';
	for (int i = 0; i < N + 1; i++) {
		cout << small[i];
	}
	cout << '\n';

	return 0;
}