백준 5430번 AC JAVA

링크텍스트

설명

최근에 골드 문제만 풀고 있는데 골드문제는 내가 푸는 방식은 항상 시간초과아니면 메모리 초과 떠서 예제출력 다 맞게 나와도 자신이 없다. 결국에는 구글링을 통해 시간을 최적화할 수 있는 방법으로 풀어야만 통과가 된다. 실버 문제까지만 해도 어떻게 풀어도 웬만해서는 통과가 되었다. 하지만 골드 문제는 그게 안된다.. 기존에는 ArrayList를 썼지만 Collections.reverse 하면 시간을 많이 잡아 먹어 통과가 안된다. 그래서 Deque를 써서 앞 또는 뒤에 원소에 접근해야만 시간초과가 나지않는다.
st = new StringTokenizer(br.readLine(), "[],"); 를 통해 대괄호와 반점을 없앨 수 있다.

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            Deque<Integer> d = new LinkedList<>();
            char[] c = br.readLine().toCharArray();
            int n = Integer.parseInt(br.readLine());

            String nums = br.readLine();
            nums = nums.replaceAll("\\[|\\]", "");

            int start = 0, end = 0;
            for (int j = 0; j < nums.length(); j++) {
                if (nums.charAt(j) == ',') {
                    d.add(Integer.parseInt(nums.substring(start, end)));
                    start = end + 1;
                }
                end++;
            }
            if (start < nums.length()) {
                d.add(Integer.parseInt(nums.substring(start, end)));
            }

            boolean error = false; 
            boolean reversed = false;

            for (int k = 0; k < c.length; k++) {
                if (c[k] == 'R') {
                    reversed = !reversed;
                } else if (c[k] == 'D') {
                    if (d.isEmpty()) { 
                        sb.append("error\n");
                        error = true;
                        break;
                    }
                    if (reversed) {
                        d.removeLast();
                    } else {
                        d.removeFirst();
                    }
                }
            }

            if (!error &&!reversed) {
                sb.append("[");
                while (!d.isEmpty()) {
                    sb.append(d.removeFirst());
                    if (!d.isEmpty()) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            }else if(!error &&reversed) {
                sb.append("[");
                while (!d.isEmpty()) {
                    sb.append(d.removeLast());
                    if (!d.isEmpty()) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            }
        }

        System.out.print(sb);
    }
}

시간 초과 난 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            ArrayList<Integer> al = new ArrayList<>();
            char[] c = br.readLine().toCharArray();
            int n = Integer.parseInt(br.readLine());

            String nums = br.readLine();
            nums = nums.replaceAll("\\[|\\]", "");

            int start = 0, end = 0;
            for (int j = 0; j < nums.length(); j++) {
                if (nums.charAt(j) == ',') {
                    al.add(Integer.parseInt(nums.substring(start, end)));
                    start = end + 1;
                }
                end++;
            }
            if (start < nums.length()) {
                al.add(Integer.parseInt(nums.substring(start, end)));
            }

            boolean error = false; 

            for (int k = 0; k < c.length; k++) {
                if (c[k] == 'R') {
                    Collections.reverse(al);
                } else if (c[k] == 'D') {
                    if (al.isEmpty()) { 
                        sb.append("error\n");
                        error = true;
                        break;
                    }
                    al.remove(0); 
                }
            }

            if (!error) {
                sb.append("[");
                for (int j = 0; j < al.size(); j++) {
                    sb.append(al.get(j));
                    if (j != al.size() - 1) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            }
        }

        System.out.print(sb);
    }
}