[백준] 5430번

기존에 직접 LinkedList를 만들어서 (삽입, 수정이 빈번하게 발생하므로) 로직을 수행하게 만들었다. 테스트케이스를 입력해서 실행했을 때 결과는 잘 나오지만 결과는 시간초과..

 

시간 복잡도를 고려했을 때 왜 시간 초과가 발생하는 지 알 수가 없었다. 다른 분의 블로그를 참고해보니 배열을 뒤집는 과정에서 시간 초과가 발생했을 것이라고 하셨다. 이 분은 Deque를 활용하셨는데 생각해보니 배열을 뒤집을 필요 없이 R 키워드가 주어지면 왼쪽에서부터 or 오른쪽에서부터만 결정하면 되는 것이었다. 이해하기 쉽게 설명해 주셔서 자주 보는 블로그인데 이번에도 역시.. 또 하나를 배워간다. 데큐 메모

[백준] 5430번 : AC - JAVA [자바]

 

 

 

 

기존 코드

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        String p, line, arr;
        int count;
        StringBuilder sb = new StringBuilder();

        while(T-- > 0) {
            p = br.readLine();
            count = Integer.parseInt(br.readLine());
            line = br.readLine();
            List<Integer> list = makeList(line);

            sb.append(solution(p, list)).append("\n");
        }

        System.out.println(sb);
    }

    private static LinkedList<Integer> makeList(String line) {
        LinkedList<Integer> list = new LinkedList<>();

        for (int i = 1; i < line.length() - 1; i += 2) {
            list.add(Integer.parseInt(String.valueOf(line.charAt(i))));
        }

        return list;
    }

    private static String solution(String p, List<Integer> list) {
        StringBuilder sb = new StringBuilder("[");

        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == 'R') {
                Collections.reverse(list);
            } else {
                if (list.isEmpty()) {
                    return "error";
                } else {
                    list.remove(0);
                }
            }
        }

        if (list.size() == 0) {
            sb.append("]");
        } else if (list.size() == 1) {
            sb.append(list.get(0)).append("]");
        } else {
            for (int i = 0; i < list.size() - 1; i++) {
                sb.append(list.get(i)).append(",");
            }
            sb.append(list.get(list.size() - 1)).append("]");
        }

        return sb.toString();
    }
}

 

 

 

 

수정한 코드

 

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(br.readLine());
        String p, line, arr;
        int count;
        StringBuilder sb = new StringBuilder();

        while(T-- > 0) {
            p = br.readLine();
            count = Integer.parseInt(br.readLine());
            line = br.readLine();
            ArrayDeque<Integer> deque = makeDeque(line);

            sb.append(solution(p, deque)).append("\n");
        }

        System.out.println(sb);
    }

    private static ArrayDeque<Integer> makeDeque(String line) {
        StringTokenizer st = new StringTokenizer(line, "[],");
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        while(st.hasMoreTokens()) {
            deque.add(Integer.parseInt(st.nextToken()));
        }

        return deque;
    }

    private static String solution(String p, ArrayDeque<Integer> deque) {
        StringBuilder sb = new StringBuilder("[");
        boolean isRight = true;

        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == 'R') {
                isRight = !isRight;
                continue;
            }

            if (isRight) {
                if (deque.isEmpty()) {
                    return "error";
                } else {
                    deque.removeFirst();
                }
            } else {
                if (deque.isEmpty()) {
                    return "error";
                } else {
                    deque.removeLast();
                }
            }
        }

        if (deque.size() > 0) {
            if (isRight) {
                sb.append(deque.pollFirst());

                while(!deque.isEmpty()) {
                    sb.append(',').append(deque.pollFirst());
                }
            } else {
                sb.append(deque.pollLast());

                while(!deque.isEmpty()) {
                    sb.append(',').append(deque.pollLast());
                }
            }
        }
        sb.append(']');

        return sb.toString();
    }
}