https://www.acmicpc.net/problem/10866

문제

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

명령은 총 여덟 가지이다.

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

입력

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

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

출력

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

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

풀이

자료구조 중 덱의 기본 연산을 이용하는 문제이다.
덱이란 기본적으로 큐의 형태지만, 앞에서는 빼기만 가능하고 뒤에서는 넣기만 가능한 큐와 달리 앞에서도 넣고 뒤에서도 뺄 수 있는 자료구조를 말한다. 쉽게 말해 앞뒤로 넣었다 뺐다 하는 것이 자유로운 자료구조이다.

자바에는 덱이 인터페이스 형태로 구현되어 있으므로 이를 이용하면 쉽게 문제를 풀 수 있다. 구현하는 방법은 다음과 같다.

import java.util.ArrayDeque;
import java.util.Deque;

public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>(); //LinkedList로도 가능

이제 문제에 주어진 명령에 대응하는 연산을 그대로 활용하면 된다.

• push_front: addFirst()
• push_back: addLast()
• pop_front: removeFirst()
• pop_back: removeLast()
• size: size()
• empty: isEmpty()
• front: peekFirst()
• back: peekLast()

여기서도 큐와 마찬가지로 add 대신 offer를, remove 대신 poll을 사용할 수 있다.

   

시간초과가 날 경우

이 문제에서 주의할 점은 시간제한이 0.5초로 빡빡한 편이기에 Scanner를 통해 입력을 받으면 시간초과로 틀릴 수 있다. 분명 제대로 했는데 왜 시간초과지? 하고 알아보니까 많은 양의 데이터를 입력받을 때에는 BufferedReader를 이용하는 것이 훨씬 더 빠르게 입력받을 수 있다고 한다.

BufferedReader는 말 그대로 버퍼에 넣어서 입력을 처리하는 것인데, Scanner에 비해 속도가 빠르다는 장점이 있긴 하지만 사용법이 조금 복잡하다. 여기에서는 이 문제에서 BufferedReader를 어떻게 썼는지만 정리해 볼 것이다.

먼저 BufferedReader는 이렇게 구현할 수 있다.

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

public static void main(String[] args) throws IOException {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
}

중요한 것은 반드시 IOException 처리를 해주어야 한다는 것이다. 쓸 때마다 try-catch를 이용할 수도 있지만, 보통은 그러면 너무 귀찮으니까 throws로 처리한다고 한다.

BufferedReader의 특징은
1. \n(엔터)를 기준으로 입력을 구분하고
2. 반드시 String 타입으로 입력을 받는다는 것이다.
이 때문에 Scanner에 비해서는 사용이 까다롭다.

 
일단 문제에서 전체 명령의 수를 입력받아야 하는데, 그러기 위해서 String타입 데이터를 int형으로 바꿔주어야 한다. 입력은 readLine()을 이용해서, 형변환은 Integer.parseInt()를 이용해서 할 수 있다.

int num = Integer.parseInt(br.readLine());

 
다음으로 명령을 입력받아야 하는데, 입력 예시에서도 볼 수 있듯이

push_back 1

처럼 한 줄에 공백을 경계로 여러 입력을 받는 경우가 있다. 이 경우 StringTokenizer이나 split()을 이용하면 공백을 기준으로 문자열을 잘라서 각각 저장할 수 있다. 여기에서는 split()을 이용하였다.

String[] command = br.readLine().split(" ");

readLine()으로 읽어들인 값을 split(" ")을 이용해 공백을 기준으로 문자열을 잘라 command라는 String 배열에 순서대로 저장하는 것이다.
이후 command[0]값을 기준으로 문제에서 주어진 명령을 구현하면 된다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class BJ_10866 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Deque<Integer> deque = new ArrayDeque<>();
		int num = Integer.parseInt(br.readLine());

		for (int i = 0; i < num; i++) {
			String[] command = br.readLine().split(" ");

			switch (command[0]) {
			case "push_front":
				deque.addFirst(Integer.parseInt(command[1]));
				break;

			case "push_back":
				deque.addLast(Integer.parseInt(command[1]));
				break;

			case "pop_front":
				if (deque.isEmpty())
					System.out.println(-1);
				else
					System.out.println(deque.removeFirst());
				break;

			case "pop_back":
				if (deque.isEmpty())
					System.out.println(-1);
				else
					System.out.println(deque.removeLast());
				break;

			case "size":
				System.out.println(deque.size());
				break;

			case "empty":
				if (deque.isEmpty())
					System.out.println(1);
				else
					System.out.println(0);
				break;

			case "front":
				if (deque.isEmpty())
					System.out.println(-1);
				else
					System.out.println(deque.peekFirst());
				break;

			case "back":
				if (deque.isEmpty())
					System.out.println(-1);
				else
					System.out.println(deque.peekLast());
				break;
			}
		}
	}

}

지금 보니까 삼항연산자를 이용해서

System.out.println(deque.isEmpty() ? -1 : deque.peekFirst());

같이 만들었으면 더 깔끔했으려나?

+

단순히 덱을 구현하는 문제라 쉬울 줄 알았더니 시간초과가 나올 줄은 정말 꿈에도 몰랐고, 그래서 알아보다 보니 새로운 입력방식인 BufferedReader에 대해서 공부할 수 있었다. 사실 더 깊게 공부해 볼까 싶기도 했었지만, 일단은 처음이니까 BufferedReader를 다뤄본 수준에서 만족하기로!