[BOJ 5430] AC

문제 출처 : https://www.acmicpc.net/problem/5430

 

풀이 : 

 

큐 문제입니다.

이 문제는 배열을 자주 뒤집어야 하는데 말 그대로 뒤집기만 하면 타임오버가 납니다.

front 와 rear의 위치만 바꿔 주어 O(1)로 뒤집은 듯한 효과를 내시면 됩니다.

 

#include<stdio.h>
 
struct reverse_queue {
    int data[100001];
    int front, rear,type;
    
    void init() { front = rear = type = 0; }
    void push(int a) { data[front++]=a; }
    int D() { return (type == 0 ? data[rear++] : data[--rear]); }
    void R() { type = (type+1)%2; int tmp = front; front = rear; rear = tmp; }
    bool empty() { return front == rear; }
}q;
 
int t,n,a,check;
char ch[100001];
 
int main()
{
    scanf("%d\n", &t);
    while (t--)
    {
        check = 0;
        q.init();
        scanf("%s", ch);
        scanf("%d\n", &n);
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
            {
                if (n == 1)scanf("[%d]", &a);
                else scanf("[%d,", &a);
            }
            else if (i == n - 1)scanf("%d]", &a);
            else scanf("%d,",&a);
            q.push(a);
        }
 
        if (n == 0)scanf("\n[]");
        for (int i = 0; ch[i] != '\0'&&!check; i++)
        {
            if (ch[i] == 'R')q.R();
            else if (ch[i] == 'D')
            {
                if (q.empty())
                {
                    printf("error\n");
                    check = 1;
                }
                else q.D();
            }
        }
        if (!check)
        {
            printf("[");
            for (int i = 0; !q.empty(); i++)
            {
                if (i == 0)printf("%d", q.D());
                else printf(",%d", q.D());
            }
            printf("]\n");
        }
    }
}