[백준] 5430

코드 1, 실패, 230818

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static String findRealWork(String str){

        Stack<Character> arr = new Stack<Character>();
        String result = "";

        for(int i = 0; i<str.length(); i++){
            if(arr.size() == 0){
                arr.add(str.charAt(i));
            } else {
                if(arr.get(arr.size()-1) == str.charAt(i)){
                    if(str.charAt(i) == 'D'){
                        arr.add(str.charAt(i));
                    } else {
                        arr.pop();
                    }
                } else {
                    arr.add(str.charAt(i));
                }
            }
        }
        for(int i = 0; i<arr.size(); i++){
            result += arr.get(i);
        }

        return result;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder;
        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i < n; i++){
            String work = br.readLine();
            work = findRealWork(work);
            int len = Integer.parseInt(br.readLine());
            String value = br.readLine();
            value = value.substring(1, value.length()-1);
            Deque<String> arr = new ArrayDeque<>();
            for(String j : value.split(",")){
                arr.add(j);
            }
            int start = 0;



            boolean check = false;
            for(int j = 0; j<work.length(); j++){
                if(work.charAt(j) == 'R'){
                    start += 1;
                } else {
                    if(arr.size() > 0){
                        if(start == 0 || start % 2 == 0){
                            arr.pollFirst();
                        } else {
                            arr.pollLast();
                        }
                    } else {
                        check = true;
                        break;
                    }
                }
            }

            if(check){
                System.out.println("error");
            } else {
                if(arr.size() > 0){
                    if(start == 0 || start % 2 == 0){
                        stringBuilder = new StringBuilder();
                        Iterator<String> iterator = arr.iterator();
                        stringBuilder.append("[");
                        while (iterator.hasNext()) {
                            stringBuilder.append(iterator.next()).append(",");
                        }
                        stringBuilder.deleteCharAt(stringBuilder.length()-1);
                        stringBuilder.append("]");
                        System.out.println(stringBuilder);

                    } else {

                        stringBuilder = new StringBuilder();
                        Iterator<String> reverseIterator = arr.descendingIterator();
                        stringBuilder.append("[");
                        while (reverseIterator.hasNext()) {
                            stringBuilder.append(reverseIterator.next()).append(",");
                        }
                        stringBuilder.deleteCharAt(stringBuilder.length()-1);
                        stringBuilder.append("]");
                        System.out.println(stringBuilder);

                    }
                } else {
                    if(len > 0){
                        System.out.println("[]");
                    } else {
                        System.out.println("error");
                    }
                }
            }
        }
    }
}

코드 2, 성공, 230818

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder;

        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String work = br.readLine();
            int len = Integer.parseInt(br.readLine());
            String value = br.readLine();
            value = value.substring(1, value.length()-1);
            Deque<String> arr = new ArrayDeque<>(Arrays.asList(value.split(",")));
            int reverse = 0;
            boolean check = false;


            for(int j = 0; j<work.length(); j++){
                if(work.charAt(j) == 'R'){
                    reverse += 1;
                } else {
                    if(arr.size() > 0){
                        if(reverse == 0 || reverse % 2 == 0){
                            arr.pollFirst();
                        } else {
                            arr.pollLast();
                        }
                    } else {
                        check = true;
                        break;
                    }
                }
            }

            if(check){
                System.out.println("error");
            } else {
                if(arr.size() > 0){
                    if(reverse == 0 || reverse % 2 == 0){
                        stringBuilder = new StringBuilder();
                        Iterator<String> iterator = arr.iterator();
                        stringBuilder.append("[").append(iterator.next());
                        while (iterator.hasNext()) {
                            stringBuilder.append(",").append(iterator.next());
                        }
                        stringBuilder.append("]");
                        System.out.println(stringBuilder);

                    } else {

                        stringBuilder = new StringBuilder();
                        Iterator<String> reverseIterator = arr.descendingIterator();
                        stringBuilder.append("[").append(reverseIterator.next());
                        while (reverseIterator.hasNext()) {
                            stringBuilder.append(",").append(reverseIterator.next());
                        }
                        stringBuilder.append("]");
                        System.out.println(stringBuilder);

                    }
                } else {
                    if(len > 0){
                        System.out.println("[]");
                    } else {
                        System.out.println("error");
                    }
                }
            }
        }
    }
}

개선 내용

1. 처음에 reverse 사용 => 시간 초과
   

2. reverse의 횟수 문제인 줄 알고 STACK을 이용해 reverse 2번씩 겹칠 때 무마시키며 reverse 횟수를 줄임 => 시간 초과

   
   

3. 2번 + deque 이용해 R일 때마다 헤더를 맨 앞 <=> 맨 뒤로 바꿔가며 제거하고 헤더 교체할 때 마다 횟수 측정해 헤더가 홀수인 경우 뒤에서부터, 0이거나 짝수인 경우 앞에서부터 출력 ==> 시간 초과

   
   

4. 3번 + 출력 전부 string builder로 바꿔도 => 시간 초과

   
   

여러 질문과 구글 내용을 찾아봐도 로직 자체의 큰 차이점을 느끼지 못해 해맸다

1번 로직을 수정과 4번 처럼 입력 포맷을 개선한 것들은 매우 바람직한 시간 복잡도 개선이지만 reverse를 줄이려던 2번 로직은 오히려 시간 복잡도가 증가하는 현상 발생

최대 100개의 테스트 케이스, 수행할 함수 1100000인데 2번 로직의 경우 스택으로 R을 최대한 줄여보는 컨셉이었고 결국 100 * (11000000) 구조를 하나 더 추가한 꼴이 되었다