1. Problem 📃
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을 출력한다.
2. Input ⌨️
[ 입력 ]
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.
문제에 나와있지 않은 명령이 주어지는 경우는 없다.
3. Output 🖨
[ 출력 ]
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
4. Example 📚
[ 입출력 예시 ]
| 예제 입력 | 예제 출력 |
|---|---|
| 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 |
| 22 front back pop_front pop_back push_front 1 front pop_back push_back 2 back pop_front push_front 10 push_front 333 front back pop_back pop_back push_back 20 push_back 1234 front back pop_back pop_back | -1 -1 -1 -1 1 1 2 2 333 10 10 333 20 1234 1234 20 |
5. Solution 🔑
문제에 나와있듯이 push_front, push_back, pop_front, pop_back, size, empty, front, back을 메서드로 구현하여 풀 것이다.
1. 문제에 명령이 총 10000개가 들어올 수 있다고 나와있으므로 배열 변수(Deque)의 크기를 10000으로 선언하여준다. 값이 앞 뒤로 모두 들어올 수 있으므로 배열은 20000칸을 설정해준다.
- 맨 앞(0)부터 시작하면 값을 앞에 넣지 못한다.
- 맨 뒤(Deque.length - 1)에서 시작하면 값을 뒤에 넣지 못한다.
- 가운데(Deque.length / 2)에서 시작해서 문제에서 처럼 앞으로만 10000개 혹은 뒤로만 10000개를 삽입할 경우가 있으므로 20000으로 지정해줬다.
- 따라서 인덱스를 가리키는 값(front, back)은 Deque.length / 2 로 초기화하여 선언해주고, size는 비어있으므로 0으로 초기화하여 선언해준다.
- push_front는 덱 앞에 값을 삽입해주는 명령이다.
Deque의 front 인덱스에 값을 넣어주고 front를 앞으로 땡겨 앞자리의 표시를 정정해준다.
그 후, size를 ++(증가)시켜준다.
- push_back은 덱 뒤에 값을 삽입해주는 명령이다.
back을 우선 ++(증가)해준다. 그 이유는 front와 back은 같은 인덱스를 가리키고 있으므로, 우선 back을 증가시키고, size또한 하나 증가시켜준다.
그 후, Deque의 back인덱스에 값을 넣어준다.
- pop_front은 덱의 가장 앞에 값을 뽑아내는 명령이다.
만약 뽑을 값이 없다면(size == 0) -1을 출력하고 그렇지 않다면 front값은 앞에 들어올 값의 위치를 나타내고 있으므로 front + 1한 인덱스를 Deque에서 뽑아 변수(n)에 담아준다.
그 후, front + 1은 아무 값(0)으로 바꿔주고, front를 한 칸 뒤로 이동(++)시켜준다. 값이 하나 빠졌으므로 사이즈를 --(감소)시켜 줄여준다. 담아두었던 값이 들은 변수 n을 반환한다.
- pop_back는 덱의 가장 뒤에 값을 뽑아내는 명령이다.
만약 뽑을 값이 없다면(size == 0) -1을 출력하고 그렇지 않다면 Deque에 back인덱스에 존재하는 값을 변수(n)에 담아준다. back의 값을 한 칸 앞으로 이동(--)시켜주고 값이 하나 빠졌으므로 사이즈를 --(감소)시켜 줄여준다. 담아두었던 값이 들은 변수 n을 반환한다.
- size는 덱의 크기를 나타내는 명령이다.
size변수 값을 그대로 반환해준다.
- empty는 덱에 값의 유무를 알려주는 명령이다.
size변수의 값이 0이라면 비어있으므로 -1을 반환해주고 그렇지 않다면 0을 반환해준다.
- front는 덱의 가장 앞에 값을 출력하는 명령이다.
size변수의 값이 0이라면 앞 값은 존재하지않으므로 -1을 반환한다. 그렇지 않다면
Deque의 front+1 인덱스의 값을 반환한다.
- back은 덱의 가장 뒤에 값을 출력하는 명령이다.
size변수의 값이 0이라면 뒷 값은 존재하지않으므로 -1을 반환한다. 그렇지 않다면
Deque의 back 인덱스의 값을 반환한다.
- 메인 메서드에서 몇 개의 명령을 받을지에 대한 변수(N)을 선언하여 값을 입력받는다.
switch문을 이용하여 들어오는 문자열에 대응하는 case의 명령으로 메서드를 불러오며 반환된 값은 StringBuilder(sb)에 담아주고 개행시켜준다.
- 최종 StringBuilder(sb)의 값을 출력해준다.
6. Code 💻
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] Deque = new int[20000];
static int front = Deque.length/2;
static int back = Deque.length/2;
static int size = 0;
// push_front X: 정수 X를 덱의 앞에 넣는다.
public static void push_front(int val) {
Deque[front] = val;
front--;
size++;
}
// push_back X: 정수 X를 덱의 뒤에 넣는다.
public static void push_back(int val) {
back++;
size++;
Deque[back] = val;
}
// pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public static int pop_front() {
if(size == 0) {
return -1;
}
else {
int n = Deque[(front + 1)];
Deque[front+1] = 0;
front++;
size--;
return n;
}
}
// pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public static int pop_back() {
if(size == 0) {
return -1;
}
else {
int n = Deque[back];
back--;
size--;
return n;
}
}
// size: 덱에 들어있는 정수의 개수를 출력한다.
public static int size() {
return size;
}
// empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
public static int empty() {
if(size == 0) {
return 1;
}
else {
return 0;
}
}
// front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public static int front() {
if(size == 0) {
return -1;
}
else {
return Deque[front+1];
}
}
// back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
public static int back() {
if(size == 0) {
return -1;
}
else {
return Deque[back];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine(), " ");
switch(st.nextToken()) {
case "push_front" :
push_front(Integer.parseInt(st.nextToken()));
break;
case "push_back" :
push_back(Integer.parseInt(st.nextToken()));
break;
case "pop_front" :
sb.append(pop_front()).append("\n");
break;
case "pop_back" :
sb.append(pop_back()).append("\n");
break;
case "size" :
sb.append(size()).append("\n");
break;
case "empty" :
sb.append(empty()).append("\n");
break;
case "front" :
sb.append(front()).append("\n");
break;
case "back" :
sb.append(back()).append("\n");
break;
}
}
System.out.println(sb);
}
}
다른 사람이 만든 것을 소비하는 활동보다, 내가 생산적인 활동을 하는 시간이 더 많도록 생활화 하자.