[백준] 18258번 - Deque

>>문제 바로가기<<

문제 이름답게 큐를 이용하는 문제이다.

이전까지는 큐 대신 리스트를 사용하여 풀이할 수 있었는데,
이 문제는 pop부분에서 시간초과가 생긴다.

리스트는 앞쪽에 있는 데이터를 삭제할 경우,
뒤에 있는 데이터들을 앞쪽으로 하나하나 옮기는 특징이 있다.

이 과정에서 데이터가 방대할 경우 많은 시간이 걸린다.

---

FIFO과 FILO을 둘다 채택하는 Deque를 사용하여 이 문제를 풀이 할 것이다.

Deque는 기본적인 틀은 Queue의 구조이고,
앞선 데이터를 삭제하더라도 나머지 데이터를 정렬하는 과정은 없다.

하지만
먼저 들어온 데이터를 먼저 뺄수도,
나중에 들어온 데이터를 먼저 뺄수도 있는
유연성 높은 자료구조를 가진다.

주요 명령어는 다음과 같다.

Deque<Integer> q = new ArrayDeque<>();

q.add() // 데이터 추가

q.remove() // 맨 앞의 데이터 삭제. q가 비어있을 경우 예외 발생
q.poll()   // 맨 앞의 데이터 반환 후 삭제, q가 비어있을 경우 null 반환

q.pollFirst()	// q.poll()과 같은 동작
q.pollLast()	// q.poll()과 같은 동작이지만, 나중에 들어온 데이터가 대상

q.peek()	// 맨 앞의 데이터 값을 반환.

q.peekFirst()	// q.peek()과 같은 동작
q.peekLast()	// q.peek()과 같은 동작이지만, 나중에 들어온 데이터가 대상

위 정보를 바탕으로 설계한 코드는 다음과 같다.

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

class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        Deque<Integer> q = new ArrayDeque<>();
        
        int N = Integer.parseInt(br.readLine());
        
        for(int i=0; i<N; i++){
        	st = new StringTokenizer(br.readLine(), " ");
        	String inst = st.nextToken();
            
            if(inst.equals("push")){
            	int num = Integer.parseInt(st.nextToken());
                q.add(num);
            }
            
            if(inst.equals("pop")){
            	bw.write((q.isEmpty() ? "-1" : q.pollFirst()) + "\n");
            }
            
            if(inst.equals("size")){
            	bw.write(q.size() + "\n");
            }
            
            if(inst.equals("empty")){
            	bw.write((q.isEmpty() ? "1" : "0") + "\n");
            }
            
            if(inst.equals("front")){
            	bw.write((q.isEmpty() ? "-1" : q.peekFirst()) + "\n");
            }
            
            if(inst.equals("back")){
            	bw.write((q.isEmpty() ? "-1" : q.peekLast()) + "\n");
            }
        }
        bw.flush();
        bw.close();
    }
}
            

맞았습니다!!