BOJ)5430 AC

문제: icpc.me/5430

정수 배열이 주어질 때 두 종류의 쿼리를 받는다 하나는 배열 전체를 뒤집는것이고 하나는 배열의 앞에서 숫자를 버리는것이다.

쿼리의 수 length(p)와 배열의 수 n이 전부 10만이므로 쿼리를 받을 때마다 배열 전체를 직접 뒤집는다면 O(T*(length(p)*n))의 시간복잡도로 시간초과를 받을 것이다.

우리는 자료구조 deque를 통하여 R 쿼리가 들어올 때 뒤집혔다는 표시만 해준 뒤 D의 경우 앞 뒤로 뽑을 지 결정해주면 된다.

출력할때도 마찬가지로 뒤집혔는지 여부를 판단하여 앞혹은 뒤에서부터 출력해주면 된다.

이렇게 구현할 경우 시간 복잡도는 O(T*(N+P))으로 초과되지 않겠지만 시간초과를 받아서 멘붕했었는데 p의 길이를 구할 때 strlen을 써서 TLE를 받았다...

소스를 수정해주니 무난하게 AC를 받을 수 있었다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int t, n, m, x, r;
int main() {
    scanf("%d", &t);
    while (t--) {
        r = 0;
        queue<pair<int, int>> qu;
        priority_queue<int> pq;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            qu.push({ x,i });
            pq.push(x);
        }
        while (qu.size()) {
            int here = qu.front().first;
            int num = qu.front().second;
            qu.pop();
            if (pq.top() == here) {
                r++;
                pq.pop();
                if (num == m)break;
            }
            else qu.push({ here,num });
        }
        printf("%d\n", r);
    }
    return 0;
}