[C++] 백준 2529번 부등호

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

풀이

입력받는 부등호 문자는 < 이면 참, > 이면 거짓으로 벡터 is_less에 저장하고, 주어진 부등호 관계를 만족하는 문자열을 모두 벡터 ans에 저장한다. 이때 부등호 문자열을 구성하는 숫자는 중복없이 0~9로 이루어져야 하므로 숫자 i가 문자열에 사용되었는지 i번째 인덱스에 저장하도록 벡터 is_used를 도입하였다.

1. i로 시작하는 문자열을 생성한다.
2. 문자열의 마지막 숫자와 j가 부등호 관계를 만족하는지 확인한다. (i != j)
   만족할 경우, j를 문자열의 맨뒤에 덧붙인다.
3. 문자열의 길이가 k+1이 될 때까지 2의 과정을 반복하고, 문자열을 ans에 저장한다.
4. ans의 최댓값과 최솟값을 출력한다.

이때 주의할 점이 있다. 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;
}