• 문제 링크: https://www.acmicpc.net/problem/5430
• 풀이 참고: https://st-lab.tistory.com/221 (매우 감사합니다!)

설명

이 문제는 구현으로 풀 수 있었지만, 시간 초과를 해결하지 못하였다.
본인은 Collection을 통해서 배열을 뒤집었는데 덱(Deque) 자료구조를 잘 이해하고 있었다면, 뒤집지 않고 풀 수 있었다.

다음 그림처럼 큐의 원소 순서 방향을 가리키는 변수 isRight를 사용하면 된다. true라면 0번째 인덱스가 front, false이면 마지막 인덱스가 front이다.

Deque는 양방향에서 접근할 수 있는 큐이기 때문에 방향을 가리키는 변수를 두고, 방향에 따라 배열 원소를 뒤집는다.

isRight가 true라면, front는 가장 왼쪽 원소이므로 pollFirst()(removeFirst())로 맨 앞의 원소를 삭제한다.
isRight가 false이면, front는 맨 오른쪽 원소이므로 pollLast()(removeLast())로 맨 뒤의 원소를 삭제한다.

Deque에 원소가 없는데 D 연산을 하면, 에러 처리하는 방법은 다음과 같다.

• 연산 전에, Deque 사이즈를 검사하여 삭제할 요소가 있는지 검사하기 위해 size를 알아낸다.

  • if(deque.size() == 0) 이라는 조건을 붙여준다.

• 삭제하고, 예외가 발생하거나 특정 값을 던지면 에러를 출력한다.

  • poll계열을 사용한다면, null을 반환한다.
  • remove를 사용하면, try-catch문으로 예외를 처리한다.

코드

import java.io.*;
import java.util.*;

public class P5430 {
    static int T;
    static String p;
    static int n;
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        ArrayDeque<Integer> deque;

        T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            deque = new ArrayDeque<Integer>();
            p = br.readLine();
            n = Integer.parseInt(br.readLine());
            /*
            * 대괄호 와 ','를 삭제한다.
            */
            String stringArray = br.readLine();
            stringArray = stringArray.replace("[", "");
            stringArray = stringArray.replace("]", "");
            StringTokenizer st = new StringTokenizer(stringArray, ",");
            for (int j = 0; j < n; j++) {
                deque.add(Integer.parseInt(st.nextToken()));
            }
            AC(p, deque);
        }
        System.out.println(sb);
    }

    private static void AC(String p, ArrayDeque<Integer> numbers) throws IOException {
    	// 방향을 나타내는 변수를 사용한다.
        boolean isRight = true;

        for (int i = 0; i < p.length(); i++) {
        	// Reverse를 만나면 방향을 바꾸어 준다.
            if (p.charAt(i) == 'R') {
                isRight = !isRight;
                continue;
            }
            if (isRight) {
            	// 앞쪽이 시작이면, pollFirst()를 하고 null이 나오면 아무것도 없다는 것이니 error를 던진다. 
                if (numbers.pollFirst() == null) {
                    sb.append("error\n");
                    return;
                }
            } else {
            	// 맨뒤가 시작이면, pollLast()를 하고 null이 나오면 아무것도 없다는 것이니 error를 던진다.
                if (numbers.pollLast() == null) {
                    sb.append("error\n");
                    return;
                }
            }
        }

        sb.append("[");

        // 출력할 원소가 한 개 이상일 경우
        if (numbers.size() > 0) {
            if (isRight) {
                sb.append(numbers.pollFirst());
                while (!numbers.isEmpty()) {
                    sb.append(',').append(numbers.pollFirst());
                }
            } else {
                sb.append(numbers.pollLast());
                while (!numbers.isEmpty()) {
                    sb.append(',').append(numbers.pollLast());
                }
            }
        }

        sb.append(']').append('\n');
    }
}

이번 문제를 풀면서 Deque에 대해서도 알 수 있었다.

• https://st-lab.tistory.com/187