어떤 문제인가?

덱을 이용해 푸는 문제.
리스트만 가지고 풀면 $O(N)$, 덱을 이용하면 $O(1)$.

시간복잡도 비교

리스트만 이용해 뒤집기 및 첫 원소 제거 동작을 구현하면,

• 뒤집기(R) : 최대 50,000번 연산
• 첫 원소 제거(D) : 최대 100,000-1번 연산

그리고 가능한 원소 최대 개수는 100,000개.
D 연산을 10만번 한다 치면 100,000 * 50,000 = 5,000,000,000번 연산해야 하는데, 1초라는 시간 내에 실행하기란 쉽지 않다.

반면 덱은 위 연산에 대해 $O(1)$의 실행시간을 무조건 보장한다. 그래서 아무리 지지고 볶아도 주어진 명령 개수만큼의 연산만 실행하면 된다.

첫 번째 복병

다 좋은데, C언어를 쓰는 입장에서 파이썬 List마냥 [1,2,3] 이렇게 입력을 받으면 좀 귀찮다. 개행문자도 신경써야 하고, 중간에 들어가는 [, \, ]도 무시하면서 값을 받아야 하기 때문이다.

나는 이렇게 구현했다.
1. [랑 ,을 무시하고 숫자만 받는다. 마지막에 ]도 받는다.
2. 만일 비어있는 리스트라면 ]만 따로 받아낸다.

scanf()는 개행문자를 무시하기라도 하는건지 ] 이후에 오는 추가적인 개행문자를 인식하지 않고 잘만 명령 구문들을 받는다.

두 번째 복병

그래서 R, D가 들어오면 어떻게 해야 하는가?
나는 다음과 같이 구현했다.

R:
-> 뒤집힘 여부를 나타내는 k 값을 1 올린다.
D:
-> k가 홀수면 덱의 앞부분(Front) 원소를 제거한다.
-> k가 짝수면 덱의 뒷부분(Rear) 원소를 제거한다.
-> N을 1 내린다.

그리고, 결과를 표시할 때는
-> N이 0보다 작으면 error를 출력한다.
-> k가 홀수면 덱의 앞부분부터 뒷부분까지 출력한다.
-> k가 짝수면 덱의 뒷부분부터 앞부분까지 출력한다.

생각해보니까 $\mod 2$을 해서 0,1로 표현할 수도 있었겠다. 어차피 R,D 개수는 다 합해서 10만개까지니 오버플로우로 인한 문제는 없다.

내 코드

#include <stdio.h>

int A[100000],F,R;
char C[100001];

int main() {
	int T,N,i,k;
	scanf("%d",&T);
	while(T-->0) {
		scanf("%s",C);
		scanf("%d",&N);
		getchar(); getchar();
		for(i=0;i<N;i++) {
			scanf("%d",&A[i]);
			getchar();
		}
		if(!N) getchar();
		F=k=i=0; R=N-1;
		while(C[i]!=0) {
			if(C[i]=='R') k++;
			else if(C[i]=='D') {
				if(k%2==0) F+=1;
				else R-=1;
				N--;
			} i++;
		}
		if(N<0) printf("error\n");
		else {
		    printf("[");
		    if(k%2==0) {
		    	for(i=F;i<R;i++) printf("%d,",A[i]);
		    } else {
		    	for(i=R;i>F;i--) printf("%d,",A[i]);
		    }
		    if(N>0) printf("%d",A[i]);
		    printf("]\n");
		}
	}
}

제출하고 보니 내 코드가 상대적으로 짧은 편에 속했다. 어쩐 일이래. 그만큼 C를 쓰는 입장에서는 까다로운 부분이 많았음을 나타내는 것일지도.