백준 5430번: AC(java)

 

문제

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

5430번: AC

 

 

난이도 : 골드5

유형 : 구현, 자료구조, 덱, 문자열

 

접근법

처음 아이디어로 역순연산을 실제로 바꾸는 형식으로 짯으나 입력되는 배열의 길이가 길수록 엄청난 비효율을 나타대며 시간초과 에러가 나왓다.

다른 사람의 풀이를 슬쩍보니 역방향 연산을 하지않고 Boolean 변수로 역방향 여부만 체크한뒤 'D' 명령이 들어왔을때 덱의 앞부분 요소를 제거할지 뒷부분 요소를 제거할지 정하여 처리하였다.

그리고 16% 에서 틀린경우는 덱이 빈경우 error를 출력하거나 올바르지 않은 형식으로 출력했었다.

 

1. 입력된 배열을 덱에 저장한다.

2. 각각의 명령어를 수행할때 'R' 인경우 boolean 변수의 not 연산을 시행한다.

3. 'D'  명령을 만난경우 boolean 변수에따라 앞, 뒤 쪽에서 poll을 진행한다. 이때, qu가 비엇다면 error 문자열을 StringBuiler 변수에 추가한후 return 하여 함수를 빠져 나온다.

4. 모든 반복이 끝날때까지 error가 발생하지 않는다면 현재 boolean 변수에 상태에 따라 정방향, 혹은 역방향 으로 StringBuilder 변수에 추가한다.

5. 테스트 케이스만큼 2~4 과정을 반복한뒤 최종적으로 StringBuilder 변수를 출력한다.

풀이

 

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


public class BOJ5430 {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(bf.readLine());

        for(int i=0; i<testCase; i++){
            Deque<Integer> qu = new LinkedList<>();

            String commandStr = bf.readLine();
            int arrLength = Integer.parseInt(bf.readLine());
            StringTokenizer st = new StringTokenizer(bf.readLine(), "[],"); //delimiter는 이와같이 다중으로 설정 가능하다.

            for(int quIndex=0; quIndex<arrLength; quIndex++){
                qu.add(Integer.parseInt(st.nextToken()));
            }
            AC(commandStr, qu);
        }
        System.out.println(sb);
    }

    static void AC(String commandStr, Deque qu){
        Boolean isReverse = false;
        for (char command: commandStr.toCharArray()){

            if(command == 'R' ) { //Reverve 변수의 not 연산후 다음 명령 수행
                isReverse = !isReverse;
                continue;
            }

            if (isReverse){ // 역방향이면
                if(qu.pollLast() == null){
                    sb.append("error\n");
                    return;
                }
            }
            if (!isReverse){ // 정방향이면
                if(qu.pollFirst() == null){
                    sb.append("error\n");
                    return;
                }
            }
        }

        sb.append("[");
        if(!qu.isEmpty()){ // 정상적으로 큐가 비어있는 경우 [] 만 출력하기 위함 
            if (isReverse){ //역방향인 경우
                sb.append(qu.pollLast());
                int quLength = qu.size();
                for(int i=0; i<quLength; i++){
                    sb.append(","+qu.pollLast());
                }
            }else{
                sb.append(qu.pollFirst());
                int quLength = qu.size();
                for(int i=0; i<quLength; i++){
                    sb.append(","+qu.pollFirst());
                }
            }
        }
        sb.append("]\n");
    }
}