티스토리 뷰

알고리즘 관련/BOJ

BOJ)5430 AC

JASON 자손9319 2017. 2. 21. 17:36

문제: icpc.me/5430


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


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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<intint>> 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3049 다각형의 대각선  (0) 2017.03.01
BOJ)9577 토렌트  (0) 2017.02.22
BOJ)5430 AC  (0) 2017.02.21
BOJ)1966 프린터 큐  (0) 2017.02.21
BOJ)6064 카잉 달력  (0) 2017.02.21
BOJ)2787 흔한 수열 문제  (0) 2017.02.20
TAG
댓글
댓글쓰기 폼