백준 1464번 뒤집기 3 C++

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

1464번: 뒤집기 3

 

앞에서부터 순서대로 탐색하면서 사전순으로 앞선 문자를 뒤로 보내고 마지막에 뒤집으면 된다.

 

뒤로 보내는 방법은 s[0] ~ s[n-1] 까지 뒤집은 뒤 s[0]~s[n]까지 다시 뒤집으면 되는데, 이 결과는 s[n] + s[0] ~ s[n-1]과 같다.

 

s[n-1] < s[n] 이라면 s[n] + s[0] ~ s[n-1]

s[n-1] >= s[n] 이라면 s[0] ~ s[n-1] + s[n]

 

마지막에 뒤집으면 사전순으로 제일 앞선 문자열이 나온다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

string str;

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

    cin >> str;
    string ans = "";
    ans += str[0];
    for (int i = 1; i < str.length(); i++) {
        if (ans[i - 1] < str[i]) {
            ans = str[i] + ans;
        }
        else {
            ans += str[i];
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
}