[백준 C++] 13417번 : 카드 문자열

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

13417번: 카드 문자열

풀이 :

- 주어지는 알파벳을 문자열의 제일 앞이나 뒤로 붙일 수 있을 때, 사전순으로 가장 빠른 문자열을 만들어야 한다.

- 문자열의 제일 앞 문자와 비교해서 같거나 작으면 앞에 붙이고, 아니면 뒤에 붙이면 된다.

 

코드 :

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

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

    int t, n;
    string ans, temp;
    char c;

    cin >> t;
    while(t--){
        cin >> n;
        ans = ""; //정답으로 쓸 문자열 초기화
        while(n--){
            temp = ""; //복사할 때 쓸 문자열 초기화
            cin >> c;
            if(ans.size() == 0){ //제일 처음 들어오는 문자는 비교없이 들어온 문자를 더해준다
                ans += c;
            }else{
                if(ans[0] < c){ //문자열의 제일 첫 문자와 비교해서 크다면 더해줘서 뒤에 붙여준다
                    ans += c;
                }else{ //작거나 같다면
                    temp += c; //temp배열에 들어온 문자를 더해서 제일 앞으로 보내주고,
                    temp += ans; //ans배열에 들어있는 문자를 더한뒤,
                    ans = temp; //다시 ans배열로 옮겨준다
                }
            }
        }
        cout << ans << '\n';
    }
}