https://www.acmicpc.net/problem/2529
입력받는 부등호 문자는 < 이면 참, > 이면 거짓으로 벡터 is_less
에 저장하고, 주어진 부등호 관계를 만족하는 문자열을 모두 벡터 ans
에 저장한다. 이때 부등호 문자열을 구성하는 숫자는 중복없이 0~9로 이루어져야 하므로 숫자 i가 문자열에 사용되었는지 i번째 인덱스에 저장하도록 벡터 is_used
를 도입하였다.
이때 주의할 점이 있다. 2번 과정을 반복할 때, 문자열의 마지막 숫자 x에 대하여 0~9중 어떠한 숫자도 x와의 부등호 관계를 만족하지 않는다면 x를 삭제해야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int k;
string str;
vector<string> ans;
vector<bool> is_less;
vector<bool> is_used(10);
void backtracking(int cnt) {
if(cnt == k) {
ans.push_back(str);
return;
}
for(int i=0; i<10; i++) {
if(is_used[i]) continue;
int prev = str[cnt] - '0';
if(is_less[cnt] && prev < i || !is_less[cnt] && prev > i) {
str += to_string(i);
is_used[i] = true;
backtracking(cnt+1);
str.pop_back();
is_used[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 c;
cin >> c;
is_less.push_back(c == '<');
}
for(int i=0; i<10; i++) {
is_used.assign(10, false);
str = to_string(i);
is_used[i] = true;
backtracking(0);
}
cout << *max_element(ans.begin(), ans.end()) << "\n";
cout << *min_element(ans.begin(), ans.end()) << "\n";
return 0;
}