[13417번] 카드 문자열 (Deque 활용)

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 데크(Deque)의 사용 방법

자료구조를 공부하며, Deque에 대한 개념 및 코딩만 해본 상태이고, 직접적인 문제를 접해본 적은 없는 문제인데

이 문제는 Deque에 대한 적절한 문제인 것 같다.

어떤 값보다 아스키 코드로 앞서는 값이면 왼쪽에, 아스키 코드로 앞서지 않는 값이면 오른쪽에 배치한다는 말은

즉, 스택과 큐를 동시에 이용할 수 있는 Deque임을 알 수 있다.

소스 코드 : 

#include <iostream>
#include <deque>
 
using namespace std;
 
 
int main()
{
    deque<char> dq;
    int tCase;
    int n;
    char val;
 
    cin >> tCase;
    for (int i = 0; i < tCase; i++)
    {
        cin >> n;
 
        for (int k = 0; k < n; k++)
        {
            cin >> val;
 
            // 처음에 들어오는 값을 받는다.
            if (dq.empty())
                dq.push_front(val);
 
            // 가장 왼쪽값보다 현재 입력받은 값이 
            // 아스키 값으로 더 크면
            else if (dq.front() < val)
                dq.push_back(val);
 
            // 가장 오른쪽값보다 현재 입력받은 값이
            // 아스키 값으로 작거나 같으면
            else
                dq.push_front(val);
        }
 
        // 모든 값을 pop하며 출력한다.
        while(!dq.empty())
        {
            cout << dq.front();
            dq.pop_front();
        }
        cout << endl;
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>