Baekjoon18258: 큐 2

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를 사용하기로 했다

import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int[] arr; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); //스트링빌더를 통해 출력 Queue 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("

");break; //비어있는지 확인 후 poll()이나 remove()를 해준다 case"size": sb.append(queue.size()).append("

");break; //size()는 어느 때나 사용할 수 있다 case"empty": sb.append(queue.isEmpty()?1:0).append("

");break; case"front":sb.append(queue.isEmpty()?-1:queue.peek()).append("

");break; //front와 back이 헷갈릴 수 있다. front는 맨 처음 들어온, 출력 예정인 자료므로 peek() case"back": sb.append(queue.isEmpty()?-1:first).append("

");break; //Queue는 마지막에 집어넣은 숫자를 알려주는 메소드가 없다. add()할 때 기록해준다 } } System.out.print(sb.toString()); }}

from http://devyoseph.tistory.com/94 by ccl(A) rewrite - 2021-10-22 20:27:45