(java) 백준 5430 - AC

www.acmicpc.net/problem/5430

5430번: AC

 

처음 문제 보고 뭐야 그냥 라이브러리 써서 뒤집으면 되네~ 일말의 의심없이 했다가 틀린문제 ㅎ,ㅎ

사실 정답률 보고 현실도피하지 않았나 싶다ㅋㅋ

문제의 핵심은 R 연산에서 뒤집으란대로 뒤집으면 안되는것..! 실제로 뒤집지 않고 뒤집은것 처럼 연산을 수행해야 한다. 

 

처음엔 ArrayList로 만들어서 Collections 라이브러리로 뒤집었다가 시간초과나고,,,, 그다음엔 Deque로 뒤집엇는데도 시간초과나서 무슨일인가 그때서야 배열 길이랑 연산자 길이를 봤다.

각각 길이가 10만이여서 아무리 Deque, stack으로 뒤집는다고 해도 최대 10억번 연산을 해야한다. 따라서 결론은 뒤집지 말아야 한다.

 

뒤집지 않기위해 front변수를 두어 앞이 어딘지를 구분해놓고 연산을 실행했다.

 

[소스코드]

 

 

import java.io.*;
import java.util.*;
 
 
public class B5430 {
    public static Deque<Integer> print(Deque<Integer> arr) {
        Deque<Integer> tmp = new LinkedList();        
        while(!arr.isEmpty()) {
            int Tmp = arr.removeFirst();
            System.out.print(Tmp+" ");
            tmp.addLast(Tmp);
        }        
        // System.out.println();    
        return tmp;
    }
    static boolean isError = false;
    static Deque<Integer> ans;
    static Deque<Integer> reversed;
    static boolean front = true; //front가 true면 정방향 , false면 역방향으로 연산해야함
    public static void AC(Deque<Integer> arr , char op) {        
        if(op == 'D') {
            //앞에 것 삭제
            if(arr.isEmpty()) {
                isError = true;
            }
            else {
                if(front) {
                    arr.pollFirst();
                }else{
                    arr.pollLast();
                }                
            }            
        }else {
            //뒤집기
            front = !front;
        }        
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0 ; i<T; i++) {
            StringBuilder Operators = new StringBuilder(br.readLine());
            int N = Integer.parseInt(br.readLine());
            StringBuilder arrText = new StringBuilder(br.readLine());
 
            String[] nums = arrText.substring(1, arrText.length()-1).split(",");
 
            ans = new LinkedList<>();
            isError = false;
            front = true;           
 
            for(int j = 0 ; j<N; j++) {
                int num = 0;
                for(int k=0 ; k<nums[j].length() ; k++) {
                    char c = nums[j].charAt(k);
                    num = num*10 + (c-'0');
                }
                ans.addLast(num);
            }         
            
            for(int j=0 ; j<Operators.length(); j++) {
                char op = Operators.charAt(j);
                AC(ans, op);
                if(isError) break;
            }
            
            if(isError) sb.append("error\n");
            else {                
                sb.append("[");
               if(!ans.isEmpty()) {
                if(front) {                
                    while(ans.size() > 1) {
                        sb.append(ans.pollFirst()+",");
                    }
                    sb.append(ans.pollFirst());
                }else {
                    while(ans.size() > 1) {
                        sb.append(ans.pollLast()+",");
                    }
                    sb.append(ans.pollLast());  
                }
            }
                sb.append("]");
                sb.append("\n");
            }
            
        }
        System.out.print(sb);
    }
}