[백준] 18258번: 큐 2

백준 18258번: 큐 2

1. 문제 설명

• 예제 입력:

  15
  push 1
  push 2
  front
  back
  size
  empty
  pop
  pop
  pop
  size
  empty
  pop
  push 3
  empty
  front

• 예제 출력 1

  1
  2
  2
  0
  1
  2
  -1
  0
  1
  -1
  0
  3

2. 문제 풀이

* 큐(Queue): 선입선출(First In First Out)로 한쪽 끝에서 삽입되고, 반대 쪽 끝에서 삭제가 된다. 디큐(dnQueue)라고 부르는 삭제 연산을 수행하는 곳을 프론트(front), 인큐(enQueue)라고 부르는 삽입 연산을 수행하는 곳을 리어(rear)라고 한다.

* 덱(deque): Stack과 Queue의 연산을 모두 지원하는 자료구조로 삽입과 삭제가 리스트의 양쪽 끝에서 모두 가능한 큐이다.

코드 1: (Scanner 사용)

import java.util.*;

public class No_18258 {

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		StringBuffer sb = new StringBuffer();
		
		Deque<Integer> que = new LinkedList<Integer>();
		
		int cnt=sc.nextInt();
		int[] arr= new int[cnt];
		
		for(int i=0;i<cnt;i++) {
			String str=sc.next();
			
			if(str.contains("push")) {
				int num=sc.nextInt();
				que.add(num);
			}else if(str.equals("pop")) {
				if(!que.isEmpty()) {
					sb.append(que.poll()+"\n");
				}
				else {
					sb.append(-1+"\n");
				}
			}
			else if(str.equals("size")) {
				sb.append(que.size()+"\n");
			}
			else if(str.equals("empty")) {
				if(!que.isEmpty()) {
					sb.append(0+"\n");
				}
				else
					sb.append(1+"\n");
			}
			else if(str.equals("front")) {
				if(!que.isEmpty())
					sb.append(que.peek()+"\n");
				else 
					sb.append(-1+"\n");
			}
			else if(str.equals("back")) {
				if(!que.isEmpty())
					sb.append(que.getLast()+"\n");
				else 
					sb.append(-1+"\n");
			}
		}
		System.out.println(sb);
		
	}

코드 1: 실행 결과

• 시간초과 발생!
  
  

코드 2: (BufferedReader 사용)

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

public class No_18258 {

	public static void main(String[] args) throws IOException {
		
		//Scanner sc=new Scanner(System.in);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		
		Deque<Integer> que = new LinkedList<Integer>();
		
		int cnt=Integer.parseInt(br.readLine());
		int[] arr= new int[cnt];
		
		for(int i=0;i<cnt;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine(), " ");
			String str=st.nextToken();
			if(str.equals("push")) {
				int num=Integer.parseInt(st.nextToken());
				que.add(num);
			}else if(str.equals("pop")) {
				if(!que.isEmpty()) {
					sb.append(que.poll()+"\n");
				}
				else {
					sb.append(-1+"\n");
				}
			}
			else if(str.equals("size")) {
				sb.append(que.size()+"\n");
			}
			else if(str.equals("empty")) {
				if(!que.isEmpty()) {
					sb.append(0+"\n");
				}
				else
					sb.append(1+"\n");
			}
			else if(str.equals("front")) {
				if(!que.isEmpty())
					sb.append(que.peek()+"\n");
				else 
					sb.append(-1+"\n");
			}
			else if(str.equals("back")) {
				if(!que.isEmpty())
					sb.append(que.getLast()+"\n");
				else 
					sb.append(-1+"\n");
			}
		}
		System.out.println(sb);
		
	}

코드 2: 실행 결과