[백준] 5430번 : AC

5430번: AC

---

[Deque, 문자열]

문제는 상당히 직관적이고 길지 않아서 이해하는데 어려움은 없지만, 생각한 것을 구현을 할 수 있느냐에 관한 문제와 시간, 메모리의 효율 그리고 자료구조 덱(Deque)을 알고 있는가에 대한 문제가 있다.

 

아, 그리고 원소의 값으로 주어지는 것이 한 자릿수가 아님에 절대로 유의하자. 이 점을 간과하여 덱을 쓰지않고 문자열 객체로만 할 수 있을 줄 알았으나, 원소의 값은 1 이상 100 이하이다.

 

덱이란 간단히 말해, 큐(Queue)가 선입선출(First-in First-out, FIFO)이라면, 덱은 양방향에서 삽입 및 반출이 가능한 자료구조이다. 문제에서 주어진 함수 R, D가 있는데 R이 나올 때 마다 이를 뒤집는다면, 두세번 쯤이야 문제없지만, 최대 10만번의 함수가 존재할 수 있기에 뒤집는 것은 사용하지 않는 것이 좋다.

 

나는 뒤집힌 상태 또는 뒤집히지 않은 상태를 boolean 타입 변수에 저장했고, 그에 따라 삭제도 앞에서 혹은 뒤에서 진행했다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

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

        StringBuilder result = new StringBuilder();
        for(int a=0; a<t; a++){

            boolean error = false;
            boolean reverse = false;
            Deque<String> deque = new LinkedList<>();

            /* cmd : R, D를 한줄에 받음 */
            String cmd = br.readLine();
            int n = Integer.parseInt(br.readLine());
            /* arr: [1,2,3,59,5,...,100 */
            String arr = br.readLine();
            /* arr: 1,2,3,59,5,...,100 */
            arr = arr.substring(1, arr.length() - 1);

            StringTokenizer st = new StringTokenizer(arr, ",");

            /* ','를 기준으로 숫자만 추출해 덱에 삽입 */
            for(int i=0; i<n; i++) { deque.add(st.nextToken()); }

            /* 덱의 메서드를 최대한 사용하지 않기 위해 원소의 개수 n을 직접 관리 (시간적 효율성) */
            /* R, D 함수를 차례로 수행 */
            for(char c:cmd.toCharArray()){

                if(c == 'R') reverse = !reverse;
                else{
                    /* error 인지 확인 */
                    if(n - 1 < 0) {
                        error = true;
                        break;
                    }

                    if(reverse) { //역방향
                        deque.pollLast();
                        n--;
                    }
                    else{ //정방향
                        deque.poll();
                        n--;
                    }
                }
            }

            if (error)
                result.append("error\n");
            else{
                result.append('[');

                for(int i=0; i<n; i++)
                    result.append(reverse? deque.pollLast() : deque.poll()).append(i == n-1? "" : ',');

                result.append(']').append('\n');
            }
        }
        System.out.print(result);
    }
}