[BOJ 백준] 13417번 카드 문자열

문제

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

13417번: 카드 문자열

접근

알파벳이 적힌 카드가 n장이 있을 때 이 카드를 순서대로 뽑아서 내가 가진 알파벳 카드들의 왼쪽 혹은 오른쪽에 배치할 수 있다. 이렇게 배치했을 때 사전 순으로 가장 빠른 문자열을 출력해주는 문제이다. 따라서 뽑은 알파벳이 현재 내가 가진 문자열의 가장 앞의 알파벳보다 사전 순으로 빠르다면 문자열의 가장 앞에(왼쪽에), 아니라면 뒤에(오른쪽에) 배치해 주면 된다. 이런 로직을 구현하기 위해 덱(deque)을 사용하여 상황에 맞게 앞(front) 또는 뒤(back)에 문자를 넣어준 뒤 출력해 주었다.

코드

#include <iostream>
#include <deque>

using namespace std;

int main() {
    int test_case, n;
    deque<char> d;
    cin >> test_case;
    for (int t = 0; t < test_case; t++) {
        char c;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> c;
            if (i == 0 || d.front() < c)
                d.push_back(c);
            else 
                d.push_front(c);
        }
        for(int i = 0; i < d.size(); i++)
            cout<<d[i];
        cout << "\n";
        d.clear();
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study