[BOJ] 5430. AC

문제 원본 : https://www.acmicpc.net/problem/5430

5430번: AC

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; ++i) {
            StringBuilder builder = new StringBuilder();
            char[] chars = br.readLine().toCharArray();
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            Deque<String> deque = new ArrayDeque<>();

            if (n == 1) {
                deque.add(s.substring(1, s.length() - 1));
            } else if (n > 1) {
                String[] elem = s.substring(1, s.length() - 1).split(",");
                for (int j = 0; j < elem.length; ++j) {
                    deque.addLast(elem[j]);
                }
            }

            boolean isError = false;
            boolean isReverse = false;
            for (int j = 0; j < chars.length; ++j) {
                if (chars[j] == 'R') {
                    isReverse = !isReverse;
                } else {
                    if (deque.isEmpty()) {
                        isError = true;
                        break;
                    }

                    if (isReverse) {
                        deque.removeLast();
                    } else {
                        deque.removeFirst();
                    }
                }
            }

            if (isError) {
                builder.append("error\n");
            } else {
                builder.append("[");
                if (isReverse) {
                    while (!deque.isEmpty()) {
                        builder.append(deque.getLast()).append(",");
                        deque.removeLast();
                    }

                } else {
                    while (!deque.isEmpty()) {
                        builder.append(deque.getFirst()).append(",");
                        deque.removeFirst();
                    }

                }

                if (builder.length() > 2) {
                    builder.deleteCharAt(builder.length() - 1);
                }

                builder.append("]\n");
            }

            bw.write(builder.toString());
        }


        bw.close();
        br.close();
    }
}

• 단순 구현 문제인데 골드 5에 낮은 정답률(19.998%)이 의아해서 풀어 보았다.
• R인 경우는 뒤집고, D인 경우는 맨 앞 원소를 삭제해야 하는데,
• ArrayList로 원소를 담고 reverse를 해버리면 시간 초과가 난다.
• 삭제도 마찬가지로 ArrayList.remove는 시간 복잡도가 O(n)이기 때문에 사용하면 안 된다.
• Deque를 사용해서 R인 경우에 boolean 값으로 상태만 바꿔주고,
• 상태에 따라 맨 앞 원소나 맨 뒤 원소를 삭제하면 시간 초과를 피할 수 있다.