문제 정리

---

주어진 배열에 R(뒤집기), D(첫 번째 요소 삭제) 연산해
최종적인 배열을 구한다

입력

test case 개수
명령어
초기 배열 길이
배열
...tc만큼 반복

출력

tc마다 최종 배열 (에러 발생시 error 문구)

idea 정리

---

배열의 크기가 최대 100,000개니까 직접 배열을 뒤집는거는 시간상 불가능하고 boolean 변수를 만들어서 처리가 가능하다.

그렇다면 문제는 삭제인데
배열과 arraylist는 사용하면 구현이 가능하긴 하지만 삭제시 shift 연산 때문에 시간초과가 발생할 것이다.

뒤집는걸 boolean 변수로 처리할거면
앞에서 삭제하는 연산과 뒤에서 삭제하는 연산이 필요한데
거기에 딱 맞는 자료구조가 deque이다.

그럼 deque를 무슨 클래스로 만들어야 할지를 정해야하는데,
ArrayDeque로 만들수도 있고 LinkedList로 만들수도 있다.
나는 아무생각없이 Arraydeque로 만들었지만 둘 중 어느것이 성능상 좋을지 궁금해서 자료를 찾아봤다.

ArrayDeque vs LinkedList
위의 포스팅을 요약하자면

누군가 ArrayDeque와 LinkedList에
요소들을 특정 길이만큼 채웠다가 모두 삭제하는 연산을 테스트 했는데

요소의 길이에 따른 성능 차이를 측정했다.
요소의 길이가 10만일 때는 근소한 차이로 ArrayDeque가 속도가 빠르고
요소의 길이가 990만일 때는 ArrayDeque가 LinkedList보다 3배정도 빠르다고 나와있다.

알고리즘 정리

---

1. R 연산이 나올 경우 boolean 값 toggle
2. D 연산
   2-1. boolean == true (뒤집힌 상태)
         -> 뒤집힌 상태이니 배열의 끝에서 삭제
   2-2. boolean == false (뒤집히지 않은 상태)
         ->배열의 앞에서 삭제
   2-3. 배열이 빈 상태이면 연산을 중단하고 error 출력
3. 주어진 연산을 모두 실행한 후 남은 배열을 형식에 맞춰 출력

구현

---

//AC
public class Main {
	static Deque<Integer> deq;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=0; t<tc; t++) {
			deq = new ArrayDeque<>();
			
			boolean isError = false;
			boolean reverse = false;
			String cmd = br.readLine();

			int arrSize = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), "[],");
			
			for(int i=0; i<arrSize; i++) {		//배열 입력
				int value = Integer.parseInt(st.nextToken());
				deq.addLast(value);
			}
			
			for(int i=0, size = cmd.length(); i<size; i++) {	//명령어 처리
				if(cmd.charAt(i)=='R') {
					reverse = !reverse;
				}
				else {
					if(deq.isEmpty()) {
						isError = true;
						break;
					}
					if(reverse) {
						deq.pollLast();
					}
					else {
						deq.pollFirst();
					}
				}
			}
			
			StringBuilder sb = new StringBuilder();
			if(isError) {
				bw.write("error\n");
			}
			else {
				for(int i=0, size=deq.size(); i<size; i++) {
					int value = reverse ? deq.pollLast() : deq.pollFirst();
					sb.append(value);
					if(i!=size-1) sb.append(',');
				}
				bw.write("[" + sb.toString() + "]" + "\n");
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

결과

---