[5430] AC

https://www.acmicpc.net/problem/5430

---

import java.util.*;

// 5430 AC
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();

		Outter: for (int i = 0; i < num; i++) {
			Deque<Integer> deque = new ArrayDeque<Integer>();
			String s = sc.next();
			int b = sc.nextInt();
			String arr = sc.next();
			int dir = 0;
			arr = arr.substring(1, arr.length() - 1);
			StringTokenizer st = new StringTokenizer(arr, ",");
			while (st.hasMoreElements()) {
				deque.add(Integer.parseInt(st.nextToken() + ""));
			}
			boolean f = true;
			for (int j = 0; j < s.length(); j++) {
				if (s.charAt(j) == 'R') {
					dir++;
				} else {
					if (deque.isEmpty()) {
						System.out.println("error");
						continue Outter;
					}

					if (dir % 2 == 0) {
						deque.pollFirst();
					} else {
						deque.pollLast();
					}

				}

			}
			if (f) {
				System.out.print("[");
				if (dir % 2 == 0) {
					while (!deque.isEmpty()) {
						System.out.print(deque.poll());
						if (!deque.isEmpty()) {
							System.out.print(",");
						}
					}
				} else {
					while (!deque.isEmpty()) {
						System.out.print(deque.pollLast());
						if (!deque.isEmpty()) {
							System.out.print(",");
						}
					}
				}
				System.out.println("]");
			}
		}
	}
}

---

Queue 의 양쪽에서 삽입삭제 연산이 가능한 Dequeue 를 사용해서 해결 할 수 있는데 문제이다. 처음에는 정답률이 19%라서 어려워보였지만, 스터디하는 친구와 같이 푸니까 해결할 수 있었다. 제일 먼저 생각할 수 있는 방법이 수행할 함수의 처음부터 끝까지 탐색하면서 R이 나오면 수를 뒤집고 D가 나오면 앞에서 하나를 삭제하면 문제를 풀 수 있다고 생각할 수 있다. 하지만 그렇게 되면 수행할 함수의 길이가 100,000 이기 때문에 당연히 시간초과가 나오게 된다. 그래서 다시 생각한 방법은 R의 개수를 카운트 하면서 R이 짝수일 때 D가 나오면 deque의 앞쪽에서 삭제 연산을 하고, R이 홀수일 때에는 D가 나오면 뒤에서 삭제연산을 하는 것이다. 그렇게 되면 반복문을 한번밖에 안돌기 때문에 O(n)만에 문제를 해결할 수 있다.

< 문제 풀이 >

1. 주어진 배열의 숫자만 따로 deque에 저장한다.

2. 이제 주어진 함수를 s.charAt() 를 이용해서 첫번째부터 끝까지 반복문을 돌면서 R의 개수를 나올 때 마다 dir에 1씩 증가시키면서 카운트 한다.

3. D를 만났을 때는 두가지 경우로 나눠야 하는데 R의 개수가 짝수일 때에는 삭제연산을 앞에서하고, R의 개수가 홀수일 때는 삭제연산을 뒤에서 한다. 만약에 deque가 비어있는데 D연산을 하려고하면 error를 출력하고 끝낸다.

4. 반복문이 끝났는데, deque가 비어있지 않으면 R의 개수가 짝수인지 홀수인지 판단하여 짝수이면 앞에서부터 빼면서 출력하고, 홀수이면 뒤에서부터 빼면서 출력한다.