[백준 5430] AC (G5)

📍 문제 

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

 

📍 문제 풀이

가장 단순하게 생각할 수 있는 방법은 배열을 뒤집는 방식이 것 같다

하지만 실제로 배열로 구현해봤을 때는 아래와 같이 시간초과가 났다

 

그렇다면,, 직접 뒤집는게 아니라 어디가 앞인지만 확인할 수 있으면 되는거 아닌가?

그렇다면 양방향으로 데이터에 접근이 가능한 구조가 필요할 것이고 그럼 Deque를 생각할 수 있었다

 

`boolean` 타입의 `reverse`를 통해서 R 연산을 처리하게 된다

만약에 원본의 상태라면 `reverse = false`이기 때문에 D 연산에 대해서 `pollFirst()`로 맨 앞의 원소를 삭제한다.

반대로 R 연산을 처리한 뒤의 `reverse = true` 상태라면 D 연산에 대해서 `pollLast()`로 맨 뒤의 원소를 삭제한다.

 

연산을 모두 끝마친 뒤에도 마찬가지로 reverse 값에 따라서 출력 방법을 다르게한다.

`reverse = false`라면 맨 앞에서부터 출력해야하므로 `removeFirst()`로 값을 출력한다.

`reverse = true`라면 반대로 맨 뒤에서부터 출력해야하므로 `removeLast()`로 값을 출력한다.

📍 전체 코드

• Deque 이용한 풀이

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

public class boj_5430 {
    static Deque<Integer> deque;

    public static void main(String[] args) throws IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int t = Integer.parseInt(br.readLine());

       while (t-- > 0) {
          String command = br.readLine();
          int n = Integer.parseInt(br.readLine());

          deque = new ArrayDeque<>();
          StringTokenizer st = new StringTokenizer(br.readLine(), "[],");
          for (int i = 0; i < n; i++) {
             deque.add(Integer.parseInt(st.nextToken()));
          }
          System.out.println(AC(command));
       }
    }

    public static String AC(String command) {
       boolean reverse = false;

       for(char c : command.toCharArray()) {
          if (c == 'R') {
             reverse = !reverse;
          }else{
             if (deque.size() == 0) {
                return "error";
             }
             if (reverse) {
                deque.removeLast();
             } else {
                deque.removeFirst();
             }
          }
       }

       StringBuilder sb = new StringBuilder();
       sb.append("[");
       while (!deque.isEmpty()) {
          if (reverse) {
             sb.append(deque.removeLast());
          }else{
             sb.append(deque.removeFirst());
          }

          if (deque.size() != 0) {
             sb.append(",");
          }
       }
       sb.append("]");
       return sb.toString();
    }

}

 

• 배열 직접 뒤집기 풀이

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

public class boj_5430 {
    static int[] arr;
    public static void main(String[] args) throws IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int t = Integer.parseInt(br.readLine());

       while (t-- > 0) {
          String command = br.readLine();
          int n = Integer.parseInt(br.readLine());

          arr = new int[n];
          StringTokenizer st = new StringTokenizer(br.readLine(), "[],");
          for (int i = 0; i < n; i++) {
             arr[i] = Integer.parseInt(st.nextToken());
          }
          System.out.println(AC(command));
       }
    }

    public static String AC(String command) {
       int start = 0;
       int end = arr.length - 1;
       for(char c : command.toCharArray()) {
          if (c == 'R') {
             // 뒤집기
             reverse(start, end);
          } else if (c == 'D') {
             if (start >= end) {
                return "error";
             }
             // 앞에 숫자 삭제
             start++;
          }


       }
       StringBuilder sb = new StringBuilder();
       if (start != -1) {
          sb.append("[");
          for (int i = start; i <= end; i++) {
             sb.append(arr[i]);
             if (i <= end - 1) {
                sb.append(",");
             }
          }
          sb.append("]");
       }
       return sb.toString();
    }

    public static void reverse(int start, int end) {
       int left = start, right = end;
       while (left < right) {
          int tmp = arr[left];
          arr[left] = arr[right];
          arr[right] = tmp;
          right--;
          left++;
       }
    }
}