자료구조[큐]_백준_5430

알고리즘 스터디를 하면서 큐에 관련된 문제를 풀었습니다. 순서대로 풀다가 마지막에 이 문제의 정답률을 보고 살짝 겁을 먹은 상태로 문제를 읽었을 때는 생각보다 쉬운데? 하고 풀었지만, 시간 초과로 몇 번이나 실패를 했습니다. 사실 아직은 시간 복잡도의 개념을 잘 몰라서 문제에서 제시되는 입력값의 범위를 고려하지 않았는데 디버그를 몇 번을 돌려보고 해 봐도 모르겠어서 포기하려던 와중,,, 문제 밑에 "덱을 활용하여 시간 복잡도를 해결하는 문제"라는 문구를 보고 다시 다른 방법을 생각해보게 되었습니다. 문제에 제시된 대로, 조건과 에러 처리를 충분히 했는데 왜 시간 초과가 날까 생각하면서 코드를 봤더니 결국 시간이 걸릴만한 코드는 배열의 순서를 뒤집는 거였던 것 같아서 그 부분만 수정했더니 코드가 제출되었습니다. ㅠㅠ 조만간 시간 복잡도 개념을 공부하고 정리해서 업로드하겠습니다. 

저의 사고과정은 이렇습니다. 

1. 큐는 front에서 출력하고, rear에 입력받는다. 
2. 근데 덱은 양쪽에서 입출력이 다 가능한데? 
3. 아! 그럼 굳이 front와 rear를 생각할 필요 없이 입출력 방향만 내가 지정하면 배열을 뒤집지 않아도 되겠네
4. 왼쪽에서 뽑고 싶으면 pollFirst를 오른쪽에서 뽑고 싶으면 pollLast를 사용하면 되잖아?
5. 결국 front가 왼쪽에 있는 것이 기본적인 큐의 구조라면, front를 오른쪽에 있다고 생각하고 입출력 방향을 반대로 해주면 뒤집은 상태로 배열을 뒤집지 않아도 뒤집은 효과를 낼 수 있는 것 아닌가? (입출력이 양쪽에서 가능한 덱의 특성 때문에) 
6. 그렇다면 입출력 방향을 결정하는 상태변수 하나만 만들어서 그 변수의 boolean값에 따라 출력 메서드를 pollLast로 할 것인지 pollFirst로 할 것인지만 생각해주자.

package Queue;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
 
public class _5430 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        //전체 테스트 케이스
        int T = Integer.parseInt(br.readLine());
        
        OUT:
        while(T--> 0) {
            ArrayDeque<Integer> q = new ArrayDeque<Integer>();
            //true이면 front가 맨 오른쪽 pollLast, false이면 front가 맨 왼쪽 pollFirst
            boolean reverse = false;
            
            //수행할 함수
            String p = br.readLine();
            //배열의 요소 개수
            int n = Integer.parseInt(br.readLine()); 
            
            //배열에 들어갈 정수
            String temp = br.readLine();
            String temp2 = temp.substring(1, temp.length()-1);
            String data[] = temp2.split(",");
 
            for(int i=0; i<n; i++) {
                q.offer(Integer.parseInt(data[i]));
            }
 
            //R 명령일때는 방향전환, D명령일때는 맨 앞쪽 요소를 뽑아서 에러체크를 하고 아니면 그냥 뽑기
            for(int i =0; i < p.length(); i++) {
                
                //데이터를 뒤집어야 하는 상황이 온다면
                if(p.charAt(i) == 'R') {
                    //reverse를 false -> true로 toggle
                    reverse = !reverse;
                    continue;
                }
                
                //명령이 D일때, 삭제 하고 에러처리
                //역방향
                if(reverse) {
                    //여기서 일단 명령이 D라면 null검사를 하기위해 값을 뺀다. 그러니까 뒤에서 또 값을 빼면 D연산을 두번 하게 되는거임
                    if(q.pollLast() == null) {//큐에 요소가 없으면..에러내라
                        sb.append("error\n");
                        continue OUT; //에러를 출력하고 해당 반복을 종료시켜버리기 -> 다음 테스트 케이스 진행하기
                    } 
                //정방향
                }else {
                    if(q.pollFirst() == null) {
                        sb.append("error\n");
                        continue OUT; //에러를 출력하고 해당 반복을 종료시켜버리기
                    } 
                }
            }//end-for
            //위의 반복문에서 모든 명령을 탐색했다. R이 나올때마다 방향을 토글로 전환해주었기 때문에, 방향은 정해졌고,
            //정해진 방향대로 D명령을 수행하여 맨 앞에 값을 뽑아서 에러체크를 먼저 수행한뒤, 에러가 나지 않으면 아무것도 하지 않고 계속 진행했다.
            //위의 조건을 모두 통과하면, 남은 요소들을 출력만 하면 된다. 
            sb.append('[');
            if(q.size()>0) {
                //역방향
                if(reverse) {//남은 값 
                    sb.append(q.pollLast());
                    while(!q.isEmpty()) {
                        sb.append(',').append(q.pollLast());
                    }
                }else {//정방향
                    sb.append(q.pollFirst());
                    while(!q.isEmpty()) {
                        sb.append(',').append(q.pollFirst());
                    }
                }
            }
            sb.append(']').append('\n');
            
        }//end-while    
        
        System.out.println(sb);
 
        
    }
}
 

 

주석을 최대한 상세하게 풀어서 작성했으니 위의 전체 코드를 참조하면서 이해해 나가는데 어려움이 없을것이라고 생각합니다. 

추가적으로 배열을 입력받을 때, 문자열에 대괄호가 포함되어 있는 것을 어떻게 분리하여 큐에 넣을 것인가에 대한 고민도 해야 합니다. 그 방법으로는 정규식을 사용하거나, StringTokenizer를 사용해서 구분자를 두개 지정해주거나, 필자처럼 문자열을 대괄호를 제외하고 슬라이싱 한 다음, split메서드로 구분자를 (,)으로 주어서 구분해도 됩니다. 

필자는 정규식을 잘 모르기 때문에,,,, 오늘은 여기서 마치고 조만간 정규식도 학습해서 기록하도록 하겠습니다.

문제 출처 : https://www.acmicpc.net/problem/5430