[백준] 5430번 - AC (Gold 5)

문제 링크

백준 5430번 - AC (Gold 5)

문제 설명

주어진 배열을 뒤집거나, 첫 번째 수를 버리는 동작을 반복하는 프로그램을 구현한다.

정답 코드 및 설명

덱으로 풀 수 있다는 설명은 있으나, 일반 배열로만 구현하였다.
거꾸로 뒤집는 과정을 줄이는 것이 시간 복잡도를 줄이는 핵심 아이디어이다.
이 풀이에서는 시작과 끝을 뒤집고, 거꾸로 읽는 것으로 뒤집는 과정을 처리하였다.
추가적으로, 두 번 연속으로 뒤집는 것은 아무것도 안하는 것과 같으므로 RR은 제거하였다.

덱을 쓰고자한다면, 아래 풀이와 유사하게 방향을 지정해줄 필요가 있다.
삭제 과정은 원래 방향이면 맨 앞의 원소를, 반대 방향이면 맨 뒤의 원소를 제거하는 방식으로 구현하면 될 것이다.

import java.io.*;

public class Main {

    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());
        String comb, xString;
        int n;
        ACarray x;
        for (int i = 0; i < T; i++) {
            comb = br.readLine();
            n = Integer.parseInt(br.readLine());
            xString = br.readLine();
            comb = comb.replaceAll("RR", ""); // 두번 뒤집기는 아무것도 안한것과 같다
            x = new ACarray(n, xString);
            out: for (int j = 0; j < comb.length(); j++) {
                if (comb.charAt(j) == 'R')
                    x.R();
                if (comb.charAt(j) == 'D') {
                    x.D();
                    if (!x.sb.isEmpty()) {
                        break out;
                    }
                }
            }
            x.print();
            bw.write(x.sb.toString());
        }
        bw.close();
    }

}

class ACarray {
    int x[], start, end, size, order;
    StringBuilder sb;

    ACarray(int n, String xString) {
        x = new int[n];
        int j = 0;
        for (int i = 1; i < xString.length() - 1; i++) {
            if (xString.charAt(i) == ',') {
                j++;
                continue;
            }
            x[j] = x[j] * 10 + xString.charAt(i) - '0';
        }
        start = end = 0;
        size = n;
        order = 1;
        sb = new StringBuilder();
    }

    public void R() { // 시작과 끝점을 바꾸고 방향(order) 뒤집기
        if (x.length == 0)
            return;
        int temp = (start - order + x.length) % x.length;
        start = (end - order + x.length) % x.length;
        end = temp;
        order *= -1;
    }

    public void D() {
        if (size == 0)
            sb.append("error\n");
        else {
            start = (start + order + x.length) % x.length;
            size--;
        }
    }

    public void print() {
        if (!sb.isEmpty())
            return;
        sb.append('[');
        int index = start;
        for (int i = 0; i < size; i++) {
            sb.append(x[index]);
            if (i != size - 1)
                sb.append(',');
            index = (index + order + x.length) % x.length;
        }
        sb.append("]\n");
    }
}