해커랭크 - Bigger is Greater

사전적 순서에서 현재 문자열 다음으로 올 문자열을 구하는 문제이다.

문제풀이 전략
사전적 순서에 따라서 다음으로 올 문자열을 찾는 알고리즘은 다음과 같다.

1. 맨 뒤에서부터 아래의 조건을 만족하는 글자를 찾는다.
   1.1. 현재 글자 이후의 글자들 중, 현재 글자보다 큰 가장 작은 글자를 찾는다.
2. 찾은 글자와 현재 글자의 위치를 서로 바꾼다.
3. 앞에서 부터 현재 글자까지는 그대로 사용하고, 이후의 부분에 대해서는 정렬한 후 붙인다.
4. 만약 1.1 조건을 만족하는 글자가 없으면 답이 없음을 반환한다.
   
   참고
   https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

위의 과정을 코드로 구현한 부분이 주석 부분이 된다.

좀 더 간편하게 풀기 위해서는 next_permutation을 사용하면 된다.

next_permutation은 모든 순열을 찾는 함수인데, 이를 활용하여 현재 문자열 이후 처음으로 나타나는 순열을 리턴하면 된다.

코드

string biggerIsGreater(string w) {
    int cnt = 0;
    do{
        if(cnt == 1)
            return w;
        cnt++;
    }while(next_permutation(w.begin(), w.end()));
    return "no answer";
    
    // for(int i=w.size()-2;i>=0;i--){
    //     int idx = -1;
    //     for(int j=w.size()-1;j>i;j--){
    //         if(w[j] > w[i]){
    //             if(idx == -1)
    //                 idx = j;
    //             else{
    //                 if(w[j] < w[idx])
    //                     idx = j;
    //             }
    //         }
    //     }
    //     if(idx == -1)
    //         continue;
    //     string ans = "";
    //     char tmp = w[idx];
    //     w[idx] = w[i];
    //     w[i] = tmp;
    //     vector<char> v;
    //     for(int j=0;j<w.size();j++){
    //         if(j <= i){
    //             ans += w[j];
    //         }else{
    //             v.push_back(w[j]);
    //         }
    //     }
    //     sort(v.begin(), v.end());
    //     for(int j=0;j<v.size();j++){
    //         ans += v[j];
    //     }
    //     return ans;
    // }
    // return "no answer";
}

출처
https://www.hackerrank.com/challenges/bigger-is-greater/problem