[백준] 5430 - AC | Java

📌 문제 정보

[5430: AC]

---

💡 접근 방식

배열 자체를 ‘R’ 연산이 주어질 때마다 뒤집으면 백퍼 시간초과가 날 것 같아서
R 상태에 따른 D 횟수를 카운트 했다.
1. R이 짝수번 등장했으면 원본 배열 상태 → D 등장 시 front_del++
2. R이 홀수번 등장했으면 뒤집힌 상태 → D 등장시 back_del++
3. 연산 마무리 후 각 카운트 횟수에 따라 요소를 제거해주면 끝

통과는 했는데 정석은 아닌 것 같아서 찾아보니 Deque를 사용해서 푸는 문제였다.

양쪽으로 입출력이 가능하다!

---

🧪 시도한 풀이

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

public class Main {

    static int front_del;
    static int back_del;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            String p = br.readLine();
            int n = Integer.parseInt(br.readLine());
            String str = br.readLine();

            int del_cnt = 0;
            for (int i = 0; i < p.length(); i++) {
                if (p.charAt(i) == 'D') del_cnt++;
            }

            if (del_cnt > n) {
                sb.append("error").append("\n");
                continue;
            }

            ArrayList<String> nums = new ArrayList<>();

            StringBuilder num = new StringBuilder();
            for (int i = 1; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (ch >= '0' && ch <= '9') {
                    num.append(ch);
                } else {
                    nums.add(num.toString());
                    num = new StringBuilder();
                }
            }

            int cnt = 0;
            front_del = 0;
            back_del = 0;

            for (int i = 0; i < p.length(); i++) {
                char op = p.charAt(i);

                if (op == 'R') {
                    cnt++;
                } else {
                    del(cnt);
                }
            }

            for (int i = n-1; i > n-1 -back_del; i--) {
                nums.remove(i);
            }

            for (int i = 0; i < front_del; i++) {
                nums.remove(0);
            }

            sb.append("[");

            if (nums.isEmpty()) {
                sb.append("]\n");
                continue;
            }

            if (cnt % 2 == 0) {
                for (String s : nums) {
                    sb.append(s).append(",");
                }
            } else {
                for (int i = nums.size() - 1; i >= 0; i--) {
                    sb.append(nums.get(i)).append(",");
                }
            }

            sb.deleteCharAt(sb.length() - 1).append("]\n");
        }
        System.out.println(sb);
    }

    public static void del(int cnt) {
        if (cnt % 2 == 0) { // 앞에서부터 제거
            front_del++;
        } else { // 뒤에서 부터 제거
            back_del++;
        }
    }

}

🔍

사실 R 등장 횟수 셀 필요 없이 flag로도 처리가 가능함

그리고 또 사실 remove하는 for문 각각 돌릴 필요 없었음

StringBuilder에 저장할 때 for문 범위만 잘 조정해줬어도 됨 ㅎ

---

✅ 코드

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

public class Main {

    static ArrayDeque<String> nums;
    static boolean flag;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            String p = br.readLine();
            int n = Integer.parseInt(br.readLine());
            String str = br.readLine();

            nums = new ArrayDeque<>();

            String substr = str.substring(1, str.length() - 1);
            if (!substr.isEmpty()) {
                String[] split = substr.split(",");
                for (String s : split) {
                    nums.addLast(s);
                }
            }

            flag = true;
            boolean error = false;

            for (int i = 0; i < p.length(); i++) {
                char op = p.charAt(i);

                if (op == 'R') {
                    flag = !flag;
                } else {
                    error = del();
                }
            }

            if (error) {
                sb.append("error").append("\n");
                continue;
            }

            sb.append("[");

            if (nums.isEmpty()) {
                sb.append("]\n");
                continue;
            }

            if (flag) {
                for (String s : nums) {
                    sb.append(s).append(",");
                }
            } else {
                while (!nums.isEmpty()) {
                    String s = nums.pollLast();
                    sb.append(s).append(",");
                }
            }

            sb.deleteCharAt(sb.length() - 1).append("]\n");

        }

        System.out.println(sb);

    }

    public static boolean del() {

        if (nums.isEmpty()) return true;

        if (flag) { // 앞에서부터 제거
            nums.removeFirst();
        } else { // 뒤에서 부터 제거
            nums.removeLast();
        }

        return false;
    }

}

---

🧠 배운 점 & 회고

Deque.. 양쪽 입출력 가능!!

---

🧾 결과

Deque를 사용하고 코드를 좀 다듬으니 최종적으로 시간을 2배 넘게 단축할 수 있었다.