백준 5340 풀이

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

AC

풀이

라이브러리 함수를 써서 R이면 실제로 뒤집어서 구현하면 정확하겠지?

라는 생각으로 처음에는 문제를 풀었다.

하지만 입력값에 비해 시간이 부족하기때문에 정확하긴 했지만 시간초과를 받았다.

그럼 이제 어떻게 시간을 줄 일 수 있을까?

시간을 줄이는 것에 고민을 많이했다. 여러가지 방법을 써보았지만 시간이 그렇게 감소하는 것 같지 않았다.

결국 질문게시판을 확인했는데, 굳이 배열을 뒤집지않고 답을 구할 수 있는 방법이 있었다.

boolean 변수를 만들어 true면 뒤집힌것, false면 그대로인것.

이렇게 처리를 하고 나중에 해당 boolean 변수에 맞게 앞에서 출력 또는 뒤에서 출력하는 식으로 할 수 있었다.

이를 구현하기 위해서는 deque이 필요하다.

그렇게 시간 초과 문제는 해결되었다. 하지만 이번에는 반례가 있어 통과하지 못했고 반례를 찾기 위해 다시 고민에 들어갔다.

빈 배열과 R만 입력받았을 경우 최종적으로 빈 배열을 출력한다.

이게 내가 미처 발견하지 못한 반례였고 이 부분을 처리해 모든 테스트를 통과했다.

참고

https://www.acmicpc.net/board/view/25456

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean visit[][];
    static int n, m;
    static int graph[][];

    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++) {
            solution(br, bw);
        }

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

    private static void solution(BufferedReader br, BufferedWriter bw) throws IOException {
        String[] op = br.readLine().split("");
        int n = Integer.parseInt(br.readLine());
        String line = br.readLine();

        String line1 = line.substring(1, line.length() - 1);
        String[] nums = line1.split(",");

        Integer[] arr = new Integer[n];
        Deque<Integer> deque;
        boolean reverse = false;
        if(line.equals("[]"))
            deque = new ArrayDeque<>();
        else {
            for (int j = 0; j < n; j++) {
                try {
                    arr[j] = Integer.parseInt(nums[j]);
                } catch (NumberFormatException e) {
                    bw.write("error\n");
                    return;
                }
            }
            deque = new ArrayDeque<>(Arrays.asList(arr));
        }
        for (String str : op) {
            if (str.equals("R")) {
                if (!deque.isEmpty()) {
                    reverse = !reverse;
                }
            } else if (str.equals("D")) {
                if (!deque.isEmpty())
                    if (reverse)
                        deque.pollLast();
                    else
                        deque.pollFirst();
                else {
                    bw.write("error\n");
                    return;
                }
            }
        }
        StringBuilder ans = new StringBuilder("[");
        if (!reverse) {
            if(!deque.isEmpty()) {
                int len = deque.size();
                for (int j = 0; j < len - 1; j++) {
                    ans.append(deque.pollFirst()).append(",");
                }
                ans.append(deque.pollFirst());
            }
        } else {
            while (deque.size()>1) {
                int a = deque.pollLast();
                ans.append(a).append(",");
            }
            ans.append(deque.pollLast());
        }
        ans.append("]");
        bw.write(ans + "\n");
    }
}