💡 문제
💬 입출력 예시
📌 풀이(소스코드)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] dq = new int[20001];
static int start = 10000, end = 10000, size = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("push_back")) {
pushBack(Integer.parseInt(st.nextToken()));
} else if (cmd.equals("push_front")) {
pushFront(Integer.parseInt(st.nextToken()));
} else if (cmd.equals("pop_front")) {
sb.append(popFront()).append("\n");
} else if (cmd.equals("pop_back")) {
sb.append(popBack()).append("\n");
} else if (cmd.equals("size")) {
sb.append(size).append("\n");
} else if (cmd.equals("empty")) {
sb.append(empty()).append("\n");
} else if (cmd.equals("front")) {
sb.append(front()).append("\n");
} else if (cmd.equals("back")) {
sb.append(back()).append("\n");
}
}
System.out.println(sb);
}
private static void pushBack(int x) {
dq[++end] = x;
size++;
}
private static void pushFront(int x) {
dq[start--] = x;
size++;
}
private static int popFront() {
if (size == 0) {
return -1;
}
size--;
return dq[++start];
}
private static int popBack() {
if (size == 0) {
return -1;
}
size--;
return dq[end--];
}
private static int empty() {
if (size == 0) {
return 1;
}
return 0;
}
private static int front() {
if (size == 0) {
return -1;
}
return dq[start + 1];
}
private static int back() {
if (size == 0) {
return -1;
}
return dq[end];
}
}📄 해설
결론부터 말하자면...
솔직히 결론부터 말하자면, 이 문제도 그냥 라이브러리 쓰면 되는 문제이다.
그러나 정수배열로 구현을 해서 덱의 내부 동작을 완전히 이해하고 싶은 사람이라면, 라이브러리도 사용해보고 정수배열도 사용해보는 것을 권장한다.
이론적으로 아는 것과 구현해본 것은 확실히 다르니까.
본론
ArrayDeque를 사용해서도 풀어보았고, 그냥 정수 배열로도 풀어보았다.- 정수 배열의 경우 필자는 원형 배열을 사용할 생각을 못했는데, 다른 풀이를 찾아보던 중 원형 배열을 사용한 풀이가 있어서 같이 첨부하고자 한다.
ArrayDeque를 사용한 코드와 원형 배열을 사용한 코드는 아래에 따로 첨부하겠다.ArrayDeque는 단순히 연산에 맞게 메소드를 호출하면 되고, 원형 배열은 코드에 주석으로 설명을 대체하겠다.- 이전에 풀었던 스택과 큐 문제와 동일하게, 명령에 맞는 연산들을 메소드로 구현해서 풀이했다.
각각의 메소드에 대한 설명은 겹치니까 생략하고, 중요한 부분인 배열을 어떻게 사용할지와 인덱스 계산은 어떻게 하는지에 대한 설명을 아래에 작성하겠다.
참고로 원래 인덱스 변수명을 `front` 와 `rear` 로 표현하지만,
메소드 이름과 겹치게 사용하기 싫어서 같은 의미인 `start` 와 `end` 로 사용했다.front인덱스와rear인덱스를 배열의 중간부터 시작하게 한다. 이유는 배열의 인덱스가 0부터 시작하는데, 덱을 배열로 구현하다보면 자칫 음수 인덱스가 되어 예외를 발생시킬 수 있기 때문이다.- 그리고 배열이 중간부터 시작하므로, 배열의 크기는 주어진 명령의 개수인 10000 의 2배로, 20001 로 선언해준다.
- 배열로 구현할 때 주의점은, 어떤 풀이를 사용하더라도
front인덱스가 가리키는 인덱스는 비어있어야한다. 즉, 실제로front인덱스에 해당하는 원소는front + 1의 위치에 존재하는 것이다. - 이렇게 하는 이유는 아래와 같은 예외를 방지하기 위함이다.
- 배열이 비어있는 상태에서 push 연산을 한다고 가정하자. 이때 push_front 를 한다면, 덱의
front는 9999가 되고, 덱의rear는 여전히 10000을 가리킬 것이다. - 덱에 원소가 하나만 들어있으면, 해당 원소가
front이자rear가 되어야 하는데, 위 경우는 그렇지 않은 것을 알 수 있다. 그러므로 덱의front에 먼저 원소를 넣고,front--를 해줘야하는 것이다.
- 배열이 비어있는 상태에서 push 연산을 한다고 가정하자. 이때 push_front 를 한다면, 덱의
- 사실 대부분의 코드 자체가 큐 구현에서 크게 벗어난 것이 없다. 단지 앞과 뒤에서의 연산을 고려해줘야하기 때문에 처음 구현해본다면 까다로울 것이다.
다른 풀이 (소스코드)
ArrayDeque 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br;
static StringTokenizer st;
static StringBuilder sb;
static int N;
static ArrayDeque<Integer> dq = new ArrayDeque<>();
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
switch (cmd) {
case "push_front":
dq.addFirst(Integer.parseInt(st.nextToken()));
break;
case "push_back":
dq.addLast(Integer.parseInt(st.nextToken()));
break;
case "pop_front":
if (dq.size() == 0) {
sb.append(-1).append("\n");
} else {
sb.append(dq.pollFirst()).append("\n");
}
break;
case "pop_back":
if (dq.size() == 0) {
sb.append(-1).append("\n");
} else {
sb.append(dq.pollLast()).append("\n");
}
break;
case "size":
sb.append(dq.size()).append("\n");
break;
case "empty":
if (dq.isEmpty()) {
sb.append(1).append("\n");
} else {
sb.append(0).append("\n");
}
break;
case "front":
if (dq.isEmpty()) {
sb.append(-1).append("\n");
} else {
sb.append(dq.peekFirst()).append("\n");
}
break;
case "back":
if (dq.isEmpty()) {
sb.append(-1).append("\n");
} else {
sb.append(dq.peekLast()).append("\n");
}
break;
}
}
System.out.println(sb);
}
}원형 배열 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final int ARRAY_SIZE = 10000;
static int[] dq = new int[ARRAY_SIZE];
static int start = 0, end = 0, size = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("push_back")) {
pushBack(Integer.parseInt(st.nextToken()));
} else if (cmd.equals("push_front")) {
pushFront(Integer.parseInt(st.nextToken()));
} else if (cmd.equals("pop_front")) {
sb.append(popFront()).append("\n");
} else if (cmd.equals("pop_back")) {
sb.append(popBack()).append("\n");
} else if (cmd.equals("size")) {
sb.append(size).append("\n");
} else if (cmd.equals("empty")) {
sb.append(empty()).append("\n");
} else if (cmd.equals("front")) {
sb.append(front()).append("\n");
} else if (cmd.equals("back")) {
sb.append(back()).append("\n");
}
}
System.out.println(sb);
}
private static void pushBack(int x) {
end = (end + 1) % ARRAY_SIZE;
dq[end] = x;
size++;
}
private static void pushFront(int x) {
dq[start] = x;
start = (start - 1 + ARRAY_SIZE) % ARRAY_SIZE;
size++;
}
private static int popFront() {
if (size == 0) {
return -1;
}
int ret = dq[(start + 1) % ARRAY_SIZE];
start = (start + 1) % ARRAY_SIZE;
size--;
return ret;
}
private static int popBack() {
if (size == 0) {
return -1;
}
int ret = dq[end];
end = (end - 1 + ARRAY_SIZE) % ARRAY_SIZE;
size--;
return ret;
}
private static int empty() {
if (size == 0) {
return 1;
}
return 0;
}
private static int front() {
if (size == 0) {
return -1;
}
return dq[(start + 1) % ARRAY_SIZE];
}
private static int back() {
if (size == 0) {
return -1;
}
return dq[end];
}
}
조금 느릴게요~