BOJ_5430_AC JAVA 풀이

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

해당 문제는 곧이 곧대로 풀면 안되는 문제다. 문자열 파싱, 문자열 연산, 자료구조 등 복합적인 구현 문제이다.

일단 reverse 연산을 수행한다면 시간복잡도가 O(n)이 나온다.

수행할 함수 p는 100,000 이므로, 최악의 경우 내 생각으론 100억 번의 연산이 나올 수 있기 때문에,

처음엔 R이 나올 때 마다 배열을 뒤집었으나, R이 짝수번 나오면 뒤집지 않고, 홀수번 나오면 뒤집게 했다.

그래도 시간초과가 나서 아예 뒤집지 않고, p(함수)를 모두 수행한 뒤 뒤집어야 한다면 배열의 뒤에서 부터 원소를 꺼내고,

뒤집지 않아도 되면, 앞에서 부터 원소를 꺼내게끔 구현했다.

자료구조 Deque을 사용하면 보다 수월하게 구현할 수 있을 것이다.

구현 코드

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

public class Main {

    public static final char R = 'R';
    public static final char D = 'D';


    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());
        while (T-- != 0){
            String cmd = br.readLine();
            Deque<Integer> deque = new ArrayDeque<>();
            String n = br.readLine();
            String arr = br.readLine();
            convertStrToDeque(deque, arr);

            // R 이 나올 때마다 reverse not 연산 해준다.
            boolean reverse = false;
            boolean errorFlag = false;
            for (char e : cmd.toCharArray()){
                if (e == R) reverse = !reverse;
                if (e == D) {
                    if (deque.isEmpty()) {
                        errorFlag = true;
                        break;
                    }
                    // 뒤집어야 한다면 뒤에서 꺼내고,
                    // 뒤집지 않아도 되면 앞에서 꺼낸다.
                    if (reverse) deque.pollLast();
                    else deque.pollFirst();
                }
            }
            if (!errorFlag){
                bw.write(resultLine(deque, reverse).toString());
            }else {
                bw.write("error");
            }
            bw.write("\n");
        }
        bw.flush();
    }
    
    public static void convertStrToDeque(Deque<Integer> deque, String arr) {
        StringBuilder num = new StringBuilder();
        for (int i = 1; i + 1 < arr.length(); i++){
            char ch = arr.charAt(i);
            if (ch != ','){
                num.append(ch);
            }else {
                deque.add(Integer.parseInt(num.toString()));
                num = new StringBuilder();
            }

        }
        if (num.length() != 0){
            deque.add(Integer.parseInt(num.toString()));
        }
    }

    public static StringBuilder resultLine(Deque<Integer> deque, boolean reverse) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        // 굳이 reverse 할 필요 없이 뒤에서 부터 꺼내거나 앞에서 부터 꺼낸다
        while (!deque.isEmpty()) {
            if (reverse){
                sb.append(deque.pollLast());
            }else {
                sb.append(deque.pollFirst());
            }
            if (deque.size() != 0){
                sb.append(",");
            }
        }
        sb.append("]");
        return sb;
    }
}