Codeforces Round #744 (Div. 3)-E1. Permutation Minimization by Deque

문제 설명

크기가 $n$인 순열 $p$가 있다.

비어있는 deque(double-ended queue)가 있다고 생각해보자. 큐는 원소를 큐의 앞과 큐의 뒤 모두 삽입이 가능한 자료구조이다. 따라서 만약 deque에 $[1, 5, 2]$가 순서대로 존재할때, 원소 $4$를 deque의 앞에 삽입하면 배열 $[4, 1, 5, 2]$가 만들어진다. 그리고 같은 원소를 이번에는 뒤에 삽입한다면 배열 $[1, 5, 2, 4]$가 만들어진다.

순열의 원소는 순서대로 $p_1$부터 시작해서 $p_n$까지 비어있는 deque에 삽입된다. deque에 원소를 삽입하기 전에 우리는 이 원소를 앞에 넣을지, 뒤에 넣을지 선택할 수 있다.

만약 순열 $p = [3, 1, 2, 4]$가 있을때, deque를 이용해서 만들 수 있는 수열은 다음과 같다.

1. deque의 끝에 3을 삽입한다. $[3]$
2. deque의 앞에 1을 삽입한다. $[1, 3]$
3. deque의 끝에 2를 삽입한다. $[1, 3, 2]$
4. deque의 끝에 4를 삽입한다. $[1, 3, 2, 4]$

우리가 구해야할 수열은 주어진 순열의 모든 원소가 deque에 삽입됐을때 만들 수 있는 수열중에서 원래 순열보다 사전순으로 가장 작은 수열을 찾아야한다.

만약 $i \le n$인 $i$가 $x_1 = y_1, x_2 = y_2, ..., x_{i - 1} = y_{i - 1}$이고 $x_i < y_i$을 만족하는 수열 $[x_1, x_2, ..., x_n]$과 $[x_1, x_2, ..., x_n]$이 존재하면 수열 $[x_1, x_2, ..., x_n]$은 수열 $[y_1, y_2, ..., y_n]$보다 사전적으로 작다.

예를 들어 수열 $[1, 3, 2, 4]$는 수열 $[1, 3, 4, 2]$보다 사전순으로 작다. 왜냐하면 처음 $[1, 3]$은 같고, 첫번째 배열의 그 다음 원소인 $2$가 두번째 배열의 그 다음 원소인 $4$보다 작기 때문이다.

Input
첫번째 줄은 테스트케이스의 수 $t (1 \le t \le 1000)$가 주어진다.

각 테스트 케이스의 첫번째 줄에는 순열의 크기 $n(2 \le n \le 2\cdot10^5)$ 가 주어진다.
두번째 줄에는 순열의 원소를 나타내는 정수 $p_i(1 \le p_i \le n$, 모든 $p_i$은 중복하지 않는다.$)$ 가 $n$개 공백을 기준으로 주어진다.

Output
각 테스트 케이스마다 정답을 출력한다.

Example
input
5
4
3 1 2 4
3
3 2 1
3
3 1 2
2
1 2
2
2 1

output
1 3 2 4
1 2 3
1 3 2
1 2
1 2

문제 접근

사용한 알고리즘: 그리디
걸린 시간 : 00:05
이 문제는 백준에서 비슷한 문제를 푼 적이 있어서 쉽게 풀 수 있었다. 어떻게 E번이 C, D보다 쉬운지는 모르겠는데, 이 사실을 조금 시간이 지나서 깨달아서 아쉬웠다. 조금만 빨리 풀었으면 등수가 더 올랐을 것 같다.

결국 deque로 만들 수 있는 사전순으로 가장 작은 수열을 찾는 문제이기 때문에 deque를 이용해야할 것이다.

간단하게 생각하면 deque에 들어가야할 원소가 deque의 맨 앞에 있는 원소보다 작으면 deque의 앞에 삽입해서 더 작게 만들고, 그 원소보다 크면 deque의 뒤에 삽입해서 크게 만드는 것을 막으면 된다. 그리고 deque가 비어있으면 다음에 올 원소를 무조건 앞에 넣으면 예외 처리가 가능하다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        deque<int> dq;
        for(int i = 0; i < n; i++){
            int num; cin >> num;
            if(dq.empty() || dq.front() > num) dq.push_front(num);
            else dq.push_back(num);
        }

        for(auto x : dq) cout << x << " ";
        cout << "\n";

    }
    return 0;
}