[알고리즘] 백준 2529

백준 2529번 부등호

해결 과정 요약

numbers 를 "9876543210"으로 초기화 시킨 뒤
next_permutation 함수를 이용해 부분순열을 구한다.
그 부분순열을 입력받은 부등호와 비교해서 타당한지 검증한다.
이 과정을 위해 check함수를 만들어준다.
check결과가 true라면(타당하다면) while문을 break하고 부분순열을 출력해준다.
다시 numbers 를 "0123456789"로 바꾸어주고 위 과정을 똑같이 해준다.

풀이

#include <bits/stdc++.h>
using namespace std;

char sign[9];
string numbers= "9876543210";
string temp;
int k;

bool check(){
    for(int i=0; i<k; i++){
        if(sign[i] == '<'){
            if(temp[i] > temp[i+1]) return false;
        }
        else{
            if(temp[i] < temp[i+1]) return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> k;
    for(int i=0; i<k; i++){
        cin >> sign[i];
    }
    do{
        if(temp == numbers.substr(0,k+1)) continue;
        temp = numbers.substr(0,k+1);
        if(check()){
            cout << temp << "\n";
            break;
        }
    }while(prev_permutation(numbers.begin(), numbers.end()));
    
    numbers = "0123456789";
    do{
        if(temp == numbers.substr(0,k+1)) continue;
        temp = numbers.substr(0,k+1);
        if(check()){
            cout << temp << "\n";
            break;
        }
    }while(next_permutation(numbers.begin(), numbers.end()));
    
    return 0;
}

코멘트

풀고나서 보니 내가 굉장히 비효율적으로 풀었다는 것을 알게되었다.
물론 모든 순열을 구해도 시간초과가 안날것을 알아서 위와 같이 풀었지만,
결국에는 최악의 상황에서 시간복잡도가 O(N!)이다.
완전탐색과 백트래킹으로 푸는 것이 베스트인듯.