3-M 순열 재귀, next_permutation

안녕하세요 sol님 ㅎㅎ

좋은 발상인데요.

do while 괜찮은 거 같지만 이거는 별로인 거 같습니다.

예를 들어

9
> < < < > > > < <

이 예제 같은 경우는

그렇게 해도 됩니다.

그런 경우 코드는 다음과 같이 됩니다.

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

using namespace std;
int K,ret;
string ret_min = "9999999999", ret_max = "0000000000";
int nums[10];
string s;
vector<char> v;
vector<int> tmp, v_max, v_min, v_per;
bool check(char ch, int a, int b){
	if(ch == '<') {
		if(a < b) {
			return true;
		}
	}
	else if(ch == '>') {
		if(a > b) {
			return true;
		}
	}
	return false;
}
 
void n_per(){
	do{	  
		bool flag = true;
		for(int i = 0; i < K; i++){
			if(!check(v[i], v_per[i], v_per[i + 1])) flag = false;
		} 
		if(flag){ 
			string ret = "";
			for(int a : v_per){
				ret += a + '0';
			}  
			ret_max = max(ret_max,ret);
			ret_min = min(ret_min,ret); 
		}

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

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

	cin >> K;

	for(int i = 0; i < K; i++){
		char tmp; cin >> tmp;
		v.push_back(tmp);
	} 
	for(int i = 0; i <= 9; i++) v_per.push_back(i);
	n_per();
	cout << ret_max << '\n';
	cout << ret_min << '\n'; 
}

어차피 같은 자릿수 비교이기 때문에 string으로 하는게 더 편해서 string으로 한점 등을 봐주세요.

다만, 이게 9가 아니면 문제가 있는데요.

예를 들어 2라고 했을 때

a b c

이 자리에 숫자가 들어가는데

a는 0 ~ 9

b는 0 ~ 9 중 한개뺀

...

이런 식으로 숫자가 들어가죠?

근데 이걸 do while로 하기에는 비효율적입니다.

do while을 기반으로 vector의 순서를 바꾸는 것뿐인데 이걸 기반으로 한다면 0 ~ 9를 집어넣고 K + 1을 slice해서 구현해야 합니다.

다음과 같이 말이죠.

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

using namespace std;
int K,ret;
string ret_min, ret_max;
int nums[10];
string s;
vector<char> v;
vector<int> tmp, v_max, v_min, v_per;
bool check(char ch, int a, int b){
	if(ch == '<') {
		if(a < b) {
			return true;
		}
	}
	else if(ch == '>') {
		if(a > b) {
			return true;
		}
	}
	return false;
}
 
void n_per(){
	do{	  
		bool flag = true;
		for(int i = 0; i < K; i++){
			if(!check(v[i], v_per[i], v_per[i + 1])) flag = false;
		} 
		if(flag){ 
			string ret = ""; 
			for(int i = 0; i < K + 1; i++) ret += v_per[i] + '0'; 
			ret_max = max(ret_max,ret);
			ret_min = min(ret_min,ret); 
		}

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

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

	cin >> K;

	for(int i = 0; i < K; i++){
		char tmp; cin >> tmp;
		v.push_back(tmp);
	} 
	for(int i = 0; i <= 9; i++) v_per.push_back(i);
	for(int i = 0; i < K + 1; i++) ret_min += '9';
	for(int i = 0; i < K + 1; i++) ret_max += '0'; 
	
	n_per();
	cout << ret_max << '\n';
	cout << ret_min << '\n'; 
}

앞의 코드와 같이 구축하고 제출해보면 맞았다고는 뜨나 출력해보면 알겠지만 012 012 ... 이런식으로 반복되는 경우의 수가 생깁니다. (012345 012435.. 이런 경우의 수중에서 앞의 3개를 SLICE하게 되니..)

방금 제출해본 모습입니다. 재귀보다 DO WHILE이 56ms로 약 5배정도 느린 모습을 볼 수 있습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.