5430번: AC

문제

AC는 정수 배열에 연산을 하기 위해 만든 언어입니다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있습니다.

• R: 배열에 있는 수의 순서를 뒤집습니다.
• D: 첫 번째 수를 버립니다. 배열이 비어있는데 D를 사용하면 에러가 발생합니다.

초기 배열과 수행할 함수들이 주어졌을 때, 최종 결과를 구하는 문제입니다.

• 입력: 첫째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스는 수행할 함수 문자열 p, 배열에 들어있는 수의 개수 n, 배열 형태의 문자열 [x_1, ..., x_n] 순서로 주어집니다.
• 출력: 각 테스트 케이스마다 수행 결과를 [x_1,x_2,...] 형태로 출력하거나, 에러가 발생한 경우 error를 출력합니다.

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

풀이: 덱(Deque)과 방향 플래그를 활용한 최적화

'R' 함수가 호출될 때마다 실제로 배열을 뒤집으면 O(N)의 시간이 소요되어, 최악의 경우 시간 초과(TLE)가 발생합니다. 이를 방지하기 위해 배열의 앞뒤에서 모두 삽입/삭제가 가능한 덱(Deque) 자료구조와 방향 상태를 나타내는 플래그 변수를 함께 사용하는 것이 핵심입니다.

1. 문자열 파싱 (StringTokenizer): 입력 배열이 [1,2,3] 형태로 주어집니다. StringTokenizer의 구분자(delimiter)로 "[,]"를 지정하면, 대괄호와 쉼표를 한 번에 무시하고 깔끔하게 숫자만 추출하여 덱에 삽입할 수 있습니다.
2. 방향 플래그 (isReverse):
   • 'R' 명령을 만나면 실제로 덱을 뒤집지 않고, isReverse = !isReverse를 통해 "현재 뒤집힌 상태"라는 표시만 변경해 줍니다.
   • 'D' 명령을 만났을 때, isReverse가 false(정방향)라면 덱의 맨 앞(pollFirst)에서 요소를 제거하고, true(역방향)라면 덱의 맨 뒤(pollLast)에서 요소를 제거합니다.
3. 에러 처리: 덱이 비어있는 상태(dq.isEmpty())에서 'D' 명령을 만나면 isError를 true로 설정하고 반복문을 즉시 중단(break)합니다. 루프가 끝난 후 isError가 true라면 "error"를 출력하고 다음 테스트 케이스로 넘어갑니다.
4. 결과 출력: 에러가 발생하지 않았다면 덱에 남은 요소들을 StringBuilder를 이용해 출력 양식에 맞게 조립합니다. 단일 while 루프 내에서 isReverse의 상태에 따라 맨 앞 또는 맨 뒤에서 요소를 꺼내어 쉼표와 함께 이어 붙여 코드를 깔끔하게 처리합니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int t = Integer.parseInt(br.readLine());
       
       while (t-- > 0) {
          String p = br.readLine();
          int n = Integer.parseInt(br.readLine());
          
          // 대괄호 '[' ']' 와 쉼표 ',' 를 구분자로 설정하여 숫자만 추출
          StringTokenizer st = new StringTokenizer(br.readLine(), "[,]");
          
          Deque<Integer> dq = new ArrayDeque<>();
          boolean isReverse = false; // 뒤집힘 상태를 기록할 플래그
          
          for (int i = 0; i < n; i++) {
             dq.addLast(Integer.parseInt(st.nextToken()));
          }

          boolean isError = false;
          
          for (char c : p.toCharArray()) {
             if (c == 'R') {
                // 실제로 뒤집지 않고 상태만 반전
                isReverse = !isReverse;
             } else if (dq.isEmpty()) {
                // 비어있는데 버리려고 하면 에러
                isError = true;
                break;
             } else if (isReverse) {
                // 역방향일 때는 맨 뒤에서 제거
                dq.pollLast();
             } else {
                // 정방향일 때는 맨 앞에서 제거
                dq.pollFirst();
             }
          }

          // 에러가 발생한 경우 처리
          if (isError) {
             bw.write("error\n");
             continue;
          }

          // 출력 양식 조립
          StringBuilder sb = new StringBuilder();
          sb.append("[");
          
          // 덱에서 남은 요소를 모두 꺼냄
          while (!dq.isEmpty()) {
             if (isReverse) {
                sb.append(dq.pollLast());
             } else {
                sb.append(dq.pollFirst());
             }
             
             // 마지막 요소가 아니라면 쉼표 추가
             if (!dq.isEmpty()) {
                sb.append(",");
             }
          }

          sb.append("]\n");
          bw.write(sb.toString());
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

구현, 자료구조, 문자열, 덱 (Deque), 파싱