[백준] 5430: AC JAVA

접근

어렵진 않은데, 생각보다 푸는 데 되게 오래 걸렸던 문제다. 구현 문제는 알고리즘에 조금 소홀해지면 바로 표가 나는 것 같다. 

 

1. 우선 처음에는 'R' 명령어가 나올 때마다 배열을 reverse하는 단순한 방식으로 작성했고, 시간초과가 났다.

2. 그래서 R이 나올 때마다 flag값을 반전시켜 앞/뒤쪽 중 어디에서 아이템을 삭제할지 정하는 방식으로 수정했다. 

3. 이번엔 시간 초과는 안났는데, 틀렸다. 질문 게시판의 반례를 모두 입력해보아도 틀린 경우가 없었는데.. 

4. 이유가 다소 어이없었다ㅠ 내가 작성한 코드의 ArrayList.toString() 함수는 "[1, 2, 3]"과 같이 각 값 사이에 공백이 추가되어 나오는데, 문제의 테스트 케이스는 "[1,2,3]"과 같이 공백이 없는 값을 요구하고 있었다.. 그래서 replaceAll로 공백을 모두 없애주니 통과했다. 

 

다른 사람들의 코드와 비교해봤을 때 실행 시간이 다소 느린 것 같아서 그 이유를 고민해봤다. 로직은 동일한데, 자료구조의 문제였던 것 같다. 내가 사용한 ArrayList는, 만약 첫 번째 아이템을 remove한다면 뒤쪽의 아이템들을 모두 앞당기는 과정이 필요하다고 한다.(by gpt) 그런데 676ms가 나온 해당 코드를 보면 Deque를 사용하고 있다. 디큐도 잘 알고 있는 자료구조였지만, 알고리즘 문제를 풀며 자주 접하게 되지는 않다보니 이를 사용할 생각을 못한 것 같다. 

 

코드

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0;t < tc;t++){
            // 입력값 저장
            char[] p = br.readLine().toCharArray();
            int n = Integer.parseInt(br.readLine());
            String[] numStrArr = br.readLine().split(",|\\[|\\]");  // 양 끝에는 빈 리스트가 올 것
            
            // 숫자 배열 전처리
            ArrayList<Integer> numArr = new ArrayList();

            for(int i = 0;i < n;i++)
                numArr.add(Integer.parseInt(numStrArr[i+1]));

            String res = solve(p, numArr);
            sb.append(res).append("\n");
        }
        
        System.out.println(sb.toString());
    }

    public static String solve(char[] commandArr, ArrayList<Integer> numArr){
        // 첫 번째 코드(시간 초과)
        /**
        int commandCnt = commandArr.length;
        for(int i = 0;i < commandCnt;i++){
            char c = commandArr[i];
            if(c == 'R'){
                Collections.reverse(numArr);
            }
            else {  // c == 'D'
                if(numArr.size() == 0)
                    return "error";
                else
                    numArr.remove(0);
            }
        }

        return numArr.toString();
        **/

        int commandCnt = commandArr.length;
        boolean reverseFlag = false;
        
        for(int i = 0;i < commandCnt;i++){
            char c = commandArr[i];
            if(c == 'R'){
                reverseFlag = !reverseFlag;
            }
            else {  // c == 'D'
                if(numArr.size() == 0)
                    return "error";
                else{
                    if(reverseFlag)
                        numArr.remove(numArr.size()-1);
                    else
                        numArr.remove(0);
                }
            }
        }

        if(reverseFlag)
            Collections.reverse(numArr);

        return numArr.toString().replaceAll(" ", "");
    }
}