[백준] 2529 부등호

[백준] 2529 부등호

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

• 직접 재귀적으로 k+1 자리 배열을 만드는 코드

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

typedef long long ll;

int k;
vector<char> sign;
vector<int> arr;
bool num[10] = { 0 };

string maxArr = "0";
string minArr = "9876543210";

//k+1자리 배열이 k개의 부등호 만족하는지 검사
bool check() {
	for (int i = 0; i < k; ++i) {
		if ((sign[i] == '<')&&(arr[i] > arr[i + 1]))
			return false;
		if((sign[i] == '>') && (arr[i] < arr[i + 1]))
			return false;
	}
	return true;
}

void solve (int digit) {
	//k+1 자리 배열 생성 완료
	if (digit == k + 1) {
		if (check()) {
			string curArr = "";
			for (int i = 0; i < k + 1; ++i) {
				curArr += to_string(arr[i]);
			}

			maxArr = max(maxArr, curArr);
			minArr = min(minArr, curArr);
		}
		return;
	}

	for (int i = 0; i <= 9; ++i) {
		if (num[i]) continue;
		num[i] = true;
		arr.push_back(i);
		solve(digit + 1);
		arr.pop_back();
		num[i] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> k;

	for (int i = 0; i < k; ++i) {
		char input;
		cin >> input;
		sign.push_back(input);
	}

	solve(0);

	cout << maxArr << "\n";
	cout << minArr << "\n";
	return 0;
}

• next_permutation을 이용하여 k+1자리 문자열을 구하는 코드

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int k;
	cin >> k;

	vector<char> vec;
	for (int i = 0; i < k; ++i) {
		char input;
		cin >> input;
		vec.push_back(input);
	}

	
	string minStr = "9876543210";
	string maxStr = "0";

	string str = "0123456789";
	do {
		string curstr = str.substr(0, k + 1);

		bool flag = true;
		for (int i = 0; i < k; ++i) {
			if (vec[i] == '<') {
				if (curstr[i] > curstr[i + 1]) {
					flag = false;
					break;
				}
			}
			else {
				if (curstr[i] < curstr[i + 1]) {
					flag = false;
					break;
				}
			}
		}
		if (flag) {
			maxStr = max(maxStr, curstr);
			minStr = min(minStr, curstr);
		}

	} while (next_permutation(str.begin(), str.end()));

	cout << maxStr << "\n" << minStr;
	return 0;
}

1년 전 코드

#include <iostream>
using namespace std;

int k;
char arr[11] = { 0 }; //부등호 배열 

//std::max() std::min()과 배열 이름 겹치지 않도록 해야
int maxx[10] = { 0 }; 
int minn[10] = { 0 };

void getmax() {
	int cnt = 1;
	int n = 9;
	for (int idx = 0; idx <= k; idx++) {
		if (arr[idx] == '<') cnt++;
		if(arr[idx] == '>' || arr[idx] == 0) {
			for (int j = 0; j < cnt; j++) {
				maxx[idx - j] = n;
				n--;
			}
			cnt = 1;
		}
	}
	return;
}

void getmin() {
	int cnt = 1;
	int n = 0;
	for (int idx = 0; idx <= k; idx++) {
		if (arr[idx] == '>') cnt++;
		if (arr[idx] == '<' || arr[idx] == 0) {
			for (int j = 0; j < cnt; j++) {
				minn[idx - j] = n;
				n++;
			}
			cnt = 1;
		}
	}
	return;
}


int main() {
	cin >> k;
	for (int i = 0; i < k; i++)
		cin >> arr[i];

	getmax();
	getmin();

	for (int i = 0; i < k+1; i++) cout << maxx[i];
	cout << endl;
	for (int i = 0; i < k+1; i++) cout << minn[i];
	return 0;
}