[백준] AC (5430번)

문제 흐름

• 주어진 문제는 덱(Deque) 자료구조를 이용해 숫자 리스트에 대한 명령을 처리하는 것입니다.
• 명령어에는 순서 반전('R')과 원소 삭제('D')가 포함되며, 이 명령을 순차적으로 수행한 결과를 배열 형태로 출력해야 합니다.
• 덱이 비어 있는 상태에서 삭제 명령을 수행하면 "error"를 출력하고 해당 테스트 케이스를 종료합니다.
• 중요한 부분은 덱의 순서 반전을 효율적으로 처리하면서 올바르게 결과를 출력하는 것입니다.

 

핵심 아이디어

1. 덱(Deque) 활용
   • 덱 자료구조는 앞뒤 양쪽에서 데이터를 삽입하고 삭제할 수 있어 양방향 연산이 빠르게 수행됩니다.
2. 순서 반전 플래그 사용
   • 매번 데이터를 뒤집는 대신, reverseFlag를 이용해 마지막 출력 시 역방향으로 처리합니다.
   • 이 접근법은 시간 복잡도를 줄여 효율성을 높여줍니다.
3. 에러 처리
   • 삭제 명령 'D'가 실행될 때, 덱이 비어 있으면 즉시 "error"를 출력하고 해당 테스트 케이스를 종료해야 합니다.

 

알고리즘 흐름

1. 입력 처리
   • 테스트 케이스 개수를 입력받고, 각 케이스마다 명령어 문자열, 덱의 크기, 숫자 리스트를 입력받습니다.
   • 덱이 비어 있지 않다면, 문자열로 받은 리스트를 덱에 삽입합니다.
2. 명령어 수행
   • 명령어를 하나씩 읽으며 다음과 같은 작업을 수행합니다:
     • 'R': reverseFlag를 토글합니다(순서를 뒤집는 대신 플래그로 처리).
     • 'D': 덱에서 원소를 삭제합니다.
       • reverseFlag가 true일 때는 뒤쪽에서, false일 때는 앞쪽에서 삭제합니다.
       • 덱이 비어 있으면 "error"를 출력하고 종료합니다.
3. 출력 처리
   • 명령어 수행이 정상적으로 끝나면 reverseFlag에 따라 덱의 순서를 맞춰 배열 형태로 출력합니다.
   • 만약 덱이 비어 있으면 []로 출력됩니다.
4. 종료 및 다음 테스트 케이스 처리
   • 각 테스트 케이스가 끝나면 결과를 출력하고 다음 테스트 케이스로 넘어갑니다.

 

 

 

---

정답은 더보기 클릭

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = Integer.parseInt(in.nextLine());

        for (int i = 0; i < n; i++) {
            String command = in.nextLine(); // 명령어 문자열 입력

            int size = Integer.parseInt(in.nextLine()); // 배열의 크기 입력

            String input = in.nextLine(); // 배열 요소 문자열 입력
            input = input.substring(1, input.length() - 1); // 양 끝의 대괄호 제거

            Deque<String> deque = new ArrayDeque<>(); // 덱 생성
            if (size > 0) { // 배열 크기가 0이 아닐 경우
                String[] elements = input.split(","); // 쉼표로 나눈 요소들을
                Collections.addAll(deque, elements); // 덱에 삽입
            }

            boolean reverseFlag = false; // 순서 반전 플래그 (초기값: false)
            boolean isError = false; // 에러 발생 여부 플래그

            // 명령어 문자열의 각 문자에 대해 처리
            for (char cmd : command.toCharArray()) {
                if (cmd == 'R') { // 'R' 명령어: 순서 반전 플래그 토글
                    reverseFlag = !reverseFlag;
                } else if (cmd == 'D') { // 'D' 명령어: 덱에서 원소 삭제
                    if (deque.isEmpty()) { // 덱이 비어있다면 에러 출력 후 종료
                        System.out.println("error");
                        isError = true;
                        break;
                    }
                    if (reverseFlag) { // 반전 상태일 때는 뒤쪽에서 삭제
                        deque.pollLast();
                    } else { // 그렇지 않으면 앞쪽에서 삭제
                        deque.pollFirst();
                    }
                }
            }

            // 에러가 발생하지 않은 경우 결과 출력
            if (!isError) {
                printDeque(deque, reverseFlag); // 덱 내용 출력
            }
        }
    }

    // 덱의 내용을 출력하는 메서드
    public static void printDeque(Deque<String> deque, boolean reverseFlag) {
        StringBuilder sb = new StringBuilder(); // 결과를 저장할 StringBuilder 사용
        sb.append("["); // 출력 형식에 맞게 대괄호 추가

        if (reverseFlag) { // 반전 상태일 경우 역순으로 출력
            Iterator<String> it = deque.descendingIterator();
            while (it.hasNext()) {
                sb.append(it.next()).append(",");
            }
        } else { // 정방향일 경우 순차적으로 출력
            Iterator<String> it = deque.iterator();
            while (it.hasNext()) {
                sb.append(it.next()).append(",");
            }
        }

        // 마지막 쉼표 제거
        if (sb.length() > 1) {
            sb.deleteCharAt(sb.length() - 1);
        }
        sb.append("]"); // 출력 형식에 맞게 대괄호 닫기

        System.out.println(sb.toString()); // 최종 결과 출력
    }
}