[BOJ 백준] - AC 5430 Java

입력받은 정수배열에 대해 정해진 명령어가 적용된 결과를 출력해야 한다.

명령어는 다음 두 가지이다.

• R : 입력받은 정수배열을 뒤집는다. (1,2,3,4 -> 4,3,2,1)
• D : 0번째 위치의 원소를 삭제한다. (1,2,3,4 -> 2,3,4)
  • 삭제할 원소가 없다면 "error"를 출력한다.

어떻게든 정렬된 결과만 얻을 수 있다면 문제는 쉽게 풀린다.

성능을 고려하지 않는다면 매 번 정렬하고, 배열의 크기를 검사하고 0번 째 원소를 출력하면 될 것이다.

하지만

100,000개까지의 숫자가 주어지는 상황에서 (java의 경우) nlogn ~ O(N^2) 의 성능을 갖는 정렬을 매 번 수행하는 것은 좋지 않다.

물리적인 정렬없이 정렬을 흉내내는 것이 포인트이다.

📌 Deque 사용

물리적인 정렬을 사용하지 않고 어떻게 오름차순 정렬된 배열의 처음과 내림차순 정렬된 배열의 처음을 얻을 수 있을까?

배열은 가만히 두고 가장 왼쪽, 가장 오른쪽 원소에 접근할 수 있다면 가능할 것이다.

Deque는 양 쪽으로 삽입, 삭제가 가능한 자료구조이다.

• pollFirst or pollLast
• offerFirst or offerLast

양 종단 삭제 연산에 O(1) 이므로 매 번 정렬을 수행하는 것보다 비교되지 않는 좋은 성능을 갖는다.

📌 Code

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

public class Q5430 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        for(int i=0;i<t;i++) {
            String command = br.readLine(); 
            int n = Integer.parseInt(br.readLine());
            
            String numsInput = br.readLine();
            String[] nums = numsInput.substring(1, numsInput.length() - 1).split(",");

            Deque<String> dq = new ArrayDeque<>();
            for (String num : nums) {
                if (num.length() > 0) dq.offer(num);
            }
            
            boolean errorFlag = false; // dq가 비어있는 상태에서 'D' 명령어를 수행할 때 발생하는 에러 플래그
            boolean isLeft = true; // 방향을 나타내는 변수 (true=왼쪽=first, false=오른쪽=last)
            for (int j = 0; j < command.length(); j++) {
                if (errorFlag) break;
                int c = command.charAt(j);
                
                switch (c) {
                    case 'R':
                        isLeft = !isLeft; // 방향 뒤집기
                        break;
                    case 'D':
                        if (dq.isEmpty()) { // dq가 빈 경우 에러 메시지 출력 후 플래그 세팅
                            sb.append("error").append("\n");
                            errorFlag = true;
                            break;
                        }
                        if (isLeft) { // 왼쪽 첫번째 원소를 삭제하는 경우 (시작)
                            dq.pollFirst();
                        } else { // 오른쪽 첫번째 원소를 삭제하는 경우 (끝)
                            dq.pollLast();
                        }
                        break;
                    default:
                        break;
                }
            }
            if (!errorFlag) {
                sb.append("[");
                boolean isFirstNumber = true; // 출력 포멧을 맞추기 위한 플래그 변수
                while (!dq.isEmpty()) {
                    // 마지막 명령어를 수행했을 때의 방향을 기준으로 출력해줘야 한다.
                    if (isLeft) { 
                        if (!isFirstNumber) sb.append(",").append(dq.pollFirst());
                        else {
                            sb.append(dq.pollFirst());
                            isFirstNumber = false;
                        }
                    } else {
                        if (!isFirstNumber) sb.append(",").append(dq.pollLast());
                        else {
                            sb.append(dq.pollLast());
                            isFirstNumber = false;
                        }
                    }
                }
                sb.append("]").append("\n");
            }
        }
        System.out.println(sb);
        br.close();
    }
}

++ 입출력 포멧 때문에 괜히 더 시간이 걸린 ...