백준 Baekjoon 2529 부등호 풀이

사용언어

Visual studio 2019 C++

문제 간단요약

k개의 부등호가 주어지고 그 사이에 들어갈 가장 큰 숫자, 작은 숫자 출력

생각하기

#include <algorithm> 큰숫자: prev_permutation(v.begin(), v.end()); 사용하기 작은숫자: next_permutation(arr,arr+N); 사용하기

prev_permutation 원리

9 - 8 - 7 의 수열이 있다고 가정하자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<int> v; // 9 8 7
	for (int i = 9; i > 6; i--)
		v.push_back(i);

	while (prev_permutation(v.begin(), v.end())) {
		for (int i = 0; i < 3; i++)
			cout << v[i] << " ";
		cout << endl;
	}
}

9 7 8
8 9 7
8 7 9
7 9 8
7 8 9

그래서 여기에 valid함수를 추가해서 부등호에 맞게 바꿔보면…

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
string sign;
bool valid(vector<int>& v) {
	for (int i = 0; i < sign.length(); i++) {
		if (sign[i] == '<' && v[i] > v[i + 1])
			return false;
		else if (sign[i] == '>' && v[i] < v[i + 1])
			return false;
	}
	return true;
}
int main() {
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		char c; cin >> c;
		sign += c;
	}
	vector<int> v; // 9 8 7
	for (int i = 9; i > 6; i--)
		v.push_back(i);

	while (1) {
		if (valid(v)) // 다 맞다면 true반환되므로..
			break;
		prev_permutation(v.begin(), v.end());
		// 9 8 7 - false이므로 다음 숫자로 넘어감
		// 9 7 8 - false
		// 8 9 7 - true 이므로 while문에서 빠져나옴
	}
}

이와같은 방법으로 작은숫자는 next_permutation을 사용해서 풀이하게 되면…

[2529 풀이]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int k;
vector<int> maxNum, minNum;
string sign;

bool valid(vector<int>& v) {
	for (int i = 0; i < sign.size(); i++) {
		if (sign[i] == '>' && v[i] < v[i + 1])
			return false;
		else if (sign[i] == '<' && v[i] > v[i + 1])
			return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> k;
	for (int i = 0; i < k; i++) {
		char t; cin >> t;
		sign += t;
	}

	for (int i = 9; i > 9 - (k + 1); i--)
		maxNum.push_back(i);
	while (1) {
		if (valid(maxNum))
			break;
		prev_permutation(maxNum.begin(), maxNum.end());
	}

	for (int i = 0; i < k + 1; i++)
		minNum.push_back(i);
	while (1) {
		if (valid(minNum))
			break;
		next_permutation(minNum.begin(), minNum.end());
	}

	for (int i = 0; i < maxNum.size(); i++)
		cout << maxNum[i];
	cout << "\n";
	for (int i = 0; i < minNum.size(); i++)
		cout << minNum[i];
	cout << "\n";
}

풀이참고: https://jaimemin.tistory.com/758