Baekjoon18258: 큐 2

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

풀이

 

배열을 사용?

배열을 이용해서 풀이가 가능한지 먼저 따져보았다.

[ 자료 1, 자료 2, 자료 3, ... , 자료 n, 빈 공간, 빈 공간, 빈 공간 ]

자료가 빈 공간에 새로 들어오는 것은 괜찮지만 자료 1을 pop하면 그 다음 과정이 조금 복잡해진다

경우 1 : 자료 1을 pop한 후 자료 2부터 모두 앞으로 당겨준다. ex) 자료 2 → 자료 1

경우 2 : 자료 2부터 위치는 냅두고 탐색하는 변수값을 +1 해준다. index[0] → index [1]

두 경우 모두 연산이 계속될수록 공간의 낭비가 발생한다.

 

Queue 클래스

직접 구현할 수 있지만 앞으로 큐와 관련된 복잡한 알고리즘을 풀이할 때마다 직접 구현할 수 없는 노릇!

Java에서 지원하는 Queue class를 사용하기로 했다. 관련 개념은 아래 링크를 참고하시길!

Java: 큐(Queue)의 개념과 사용법, 요세푸스 순열

 

Queue Class

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
	 StringBuilder sb = new StringBuilder();
     //스트링빌더를 통해 출력
     
	 Queue<Integer> queue = new LinkedList<>();
     
	 StringTokenizer st;
	 int first=0;
	 int N = Integer.parseInt(br.readLine());
	 while(N--> 0) {
     
		 st = new StringTokenizer(br.readLine()," ");
		 switch(st.nextToken()) {
         
		 case"push": first = Integer.parseInt(st.nextToken()); queue.add(first); break;
         //first 변수를 통해 back에 출력할 숫자를 기록한다
         
		 case"pop": sb.append(queue.isEmpty()?-1:queue.poll()).append("\n");break;
         //비어있는지 확인 후 poll()이나 remove()를 해준다
         
		 case"size": sb.append(queue.size()).append("\n");break;
         //size()는 어느 때나 사용할 수 있다
         
		 case"empty": sb.append(queue.isEmpty()?1:0).append("\n");break;
         
		 case"front":sb.append(queue.isEmpty()?-1:queue.peek()).append("\n");break;
         //front와 back이 헷갈릴 수 있다. front는 맨 처음 들어온, 출력 예정인 자료므로 peek()
         
		 case"back": sb.append(queue.isEmpty()?-1:first).append("\n");break;
         //Queue는 마지막에 집어넣은 숫자를 알려주는 메소드가 없다. add()할 때 기록해준다
         
		 }
	 }
     
	 System.out.print(sb.toString());
}}