[BOJ] 5430: AC (JAVA)

문제

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

 

여담

예전에 문제를 풀 때는 뒤집는 함수가 나올 때마다 배열을 뒤집어서 시간 초과가 발생했었다. 그래서 투 표인터를 사용해서 뒤집는 것을 표현했다. 근데 덱을 사용해서도 풀 수 있다는 것을 알았다.. 덱을 사용하니까 오히려 더 쉽게 풀 수 있는 듯!

 

양방향으로 수를 빼내는 문제가 나올 때는 일단 덱을 생각하는 습관을 가져야 될 듯하다.

• 양방향이 나온다? 일단 덱 생각하기!

 

풀이

함수에는 R(뒤집기)와 D(첫 번째 수 빼기)가 있다. 만약 수행할 함수가 모두 R이라면, 최종 결과는 입력 결과 그대로이거나 뒤집힌 결과일 것이다. 즉, R 함수일 때마다 배열을 직접 뒤집는 것은 비효율적이다. 이렇게 풀면 시간 초과를 만날 수 있다.

 

시간 초과가 발생하지 않으려면 R 함수가 가지는 의미를 파악해야 한다.

 

R 함수는 입력 결과를 뒤집거나 첫 번째 수를 빼는 위치를 바꾸게 한다. 따라서 투 포인터를 사용하거나 양방향으로 수를 뺄 수 있는 덱을 사용해서 배열을 직접 뒤집지 않고 문제를 풀면 된다.

 

투 포인터

isReverse라는 변수를 통해 뒤집기 여부를 판단하고, 두 개의 변수(start, end)를 사용해서 뒤집힌 경우와 뒤집히지 않은 경우의 첫 번째 수 인덱스를 기록하면 된다. 정리하면 다음과 같다. 

• 함수가 R인 경우
  • isReverse = !isReverse
• 함수가 D인 경우
  • 뒤집히지 않은 경우: start++
  • 뒤집힌 경우: end--

 

덱 (Deque)

마찬가지로 isReverse라는 변수를 통해 뒤집기 여부를 판단하고, 뒤집히지 않은 경우에는 앞에서 수를 빼고 뒤집힌 경우에는 뒤에서 수를 뺀다. 정리하면 다음과 같다. 

• 함수가 R인 경우
  • isReverse = !isReverse
• 함수가 D인 경우
  • 뒤집히지 않은 경우: deque.pollFirst()
  • 뒤집힌 경우: deque.pollLast()

 

코드

투 포인터

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

public class Main {
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            // 수행할 함수 입력받기
            String[] cmd = br.readLine().split("");
            n = Integer.parseInt(br.readLine());
            // 배열의 수 입력받기
            int[] arr = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine(), "[|]|,");
            int size = st.countTokens();
            for (int i = 0; i < size; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            AC(cmd, arr);
        }
        System.out.println(sb.toString());
    }

    public static void AC(String[] cmd, int[] arr) {
        boolean isReverse = false;
        int start = 0, end = n - 1;
        for (String p : cmd) {
            if (p.equals("R")) { // 순서 뒤집기
                isReverse = !isReverse;
            } else { // 첫 번째 수 버리기
                if (start > end) { // 배열이 비어있는 경우
                    sb.append("error\n");
                    return;
                }
                if (n == 0) continue;

                if (isReverse) { // 뒤집힌 경우(역방향)
                    end--;
                } else { // 뒤집히지 않은 경우(순방향)
                    start++;
                }
            }
        }

        sb.append("[");
        if (isReverse) { // 뒤집힌 경우(역방향)
            for (int i = end; i >= start; i--) {
                sb.append(arr[i]);
                if (i != start) sb.append(",");
            }
        } else { // 뒤집히지 않은 경우(순방향)
            for (int i = start; i <= end; i++) {
                sb.append(arr[i]);
                if (i != end) sb.append(",");
            }
        }
        sb.append("]\n");
    }
}

 

덱 (Deque)

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

public class Main {
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            // 수행할 함수 입력받기
            String[] cmd = br.readLine().split("");
            n = Integer.parseInt(br.readLine());
            // 배열의 수 입력받기
            Deque<Integer> deque = new ArrayDeque<>();
            StringTokenizer st = new StringTokenizer(br.readLine(), "[|]|,");
            int size = st.countTokens();
            for (int i = 0; i < size; i++) {
                deque.offer(Integer.parseInt(st.nextToken()));
            }
            AC(cmd, deque);
        }
        System.out.println(sb.toString());
    }

    public static void AC(String[] cmd, Deque<Integer> deque) {
        boolean isReverse = false;
        for (String p : cmd) {
            if (p.equals("R")) { // 순서 뒤집기
                isReverse = !isReverse;
            } else { // 첫 번째 수 버리기
                if (deque.isEmpty()) { // 배열이 비어있는 경우
                    sb.append("error\n");
                    return;
                }

                if (isReverse) { // 뒤집힌 경우(역방향)
                    deque.pollLast();
                } else { // 뒤집히지 않은 경우(순방향)
                    deque.pollFirst();
                }
            }
        }

        sb.append("[");
        if (isReverse) {
            while (!deque.isEmpty()) {
                sb.append(deque.pollLast());
                if (!deque.isEmpty()) sb.append(",");
            }
        } else {
            while (!deque.isEmpty()) {
                sb.append(deque.pollFirst());
                if (!deque.isEmpty()) sb.append(",");
            }
        }
        sb.append("]\n");
    }
}

---