[JAVA] 5430 - AC 💛5 : 문제에서 뒤집으라는데, 뒤집지 말라고?

들어가며

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

문제는 직관적으로 이해가 가능하다. 배열 [1,2,3,4]가 주어졌을 때 명령 "R"이라면 배열뒤집기를([4,3,2,1]), 명령 "D"라면 앞에것을 지우면 된다.([2,3,4]) 근데 명령 입력의 수와 배열의 길이가 매우 커서 시간초과가 걱정되는 문제였다.

본문으로

처음에는 아래와 같이 정답을 제출했다. 문제에서 뒤집으란 말을 진짜로 뒤집기 위해 tempQ에 담아서 뒤집는 방식으로 구현했다....

public class Main {

    static int T, n;
    static String p, arr;

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

        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            boolean isError = false;
            p = bf.readLine();
            n = Integer.parseInt(bf.readLine());
            arr = bf.readLine();
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            for (int i = 1; i < arr.length() - 1; i += 2) {
                deque.addLast(Integer.parseInt(String.valueOf(arr.charAt(i))));
            }

            for (int i = 0; i < p.length(); i++) {
                char oper = p.charAt(i);
                if (oper == 'R') {
                    ArrayDeque<Integer> tempQ = new ArrayDeque<>();
                    while (!deque.isEmpty()) {
                        tempQ.addFirst(deque.pollFirst());
                    }
                    deque = tempQ;
                } else { // D
                    if (deque.isEmpty()) {
                        isError = true;
                        break;
                    }
                    deque.pollFirst();
                }
            }

            if (isError) {
                sb.append("error");
            } else {
                int size = deque.size();
                sb.append("[");
                for (int i = 0; i < size; i++) {
                    sb.append(deque.pollFirst());
                    if (i != size - 1) {
                        sb.append(",");
                    }
                }
                sb.append("]");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

}

바로 시간초과 난다 ㅎㅎ. 애초에 R이 나올때마다 deque자료구조를 뒤집는 것은 O(N)인데, 배열과 명령의 최댓값은 각각 100,000으로 10만^10만 이니 무조건 시간초과가 난다.

---

이 문제의 핵심은 실제로 뒤집지 않는 것이 포인트였다! 뒤집었는지 안뒤집었는지 플래그 변수만 잘 관리해준다면, "D"명령이 들어왔을때도 아래처럼 처리하면 된다.

reverse == false → 앞에서 제거
reverse == true → 뒤에서 제거

그리고 출력도 reverse가 true인 상태라면 반대로 출력하면 되는것이다! 정답 코드는 아래와 같이 작성했다.

public class Main {

    static int T, n;
    static String p, arr;

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

        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            boolean isError = false;
            boolean isReverse = false;
            p = bf.readLine();
            n = Integer.parseInt(bf.readLine());
            arr = bf.readLine();
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            if (n > 0) {
                String[] nums = arr.substring(1, arr.length() - 1).split(",");
                for (String num : nums) {
                    deque.addLast(Integer.parseInt(num));
                }
            }
            for (int i = 0; i < p.length(); i++) {
                char oper = p.charAt(i);
                if (oper == 'R') {
                    isReverse = !isReverse;
                } else { // D
                    if (deque.isEmpty()) {
                        isError = true;
                        break;
                    }
                    if (isReverse) {
                        deque.pollLast();
                    } else {
                        deque.pollFirst();
                    }
                }
            }

            if (isError) {
                sb.append("error");
            } else {
                int size = deque.size();
                sb.append("[");

                if (isReverse) {
                    for (int i = 0; i < size; i++) {
                        sb.append(deque.pollLast());
                        if (i != size - 1) {
                            sb.append(",");
                        }
                    }
                } else {
                    for (int i = 0; i < size; i++) {
                        sb.append(deque.pollFirst());
                        if (i != size - 1) {
                            sb.append(",");
                        }
                    }
                }
                sb.append("]");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }

}

바로 통과한다!

마무리하며

이렇게 뒤집는 연산을 실제로 뒤집지 않고 간단하게 처리했다. 시간복잡도도 훨씬 줄어들었다.

 

뒤집으라고 해서 temp queue도 두고, 투포인터로 조금씩 줄여볼 생각도 해봤는데, flag변수로 뒤집었는지 여부만 확인하면 된다는 생각은 정말 혁신적이었다. 이렇게 뒤집는 문제들은 시간복잡도가 위험한 경우가 많던데 이 Thinking은 꼭 기억해서 나중에 써먹어야겠다~!

힘내자 🔥🔥