[Baekjoon/Programmers] 10866 덱
10866 덱문제 해결 과정.
이번엔 덱을 구현하는 문제를 풀어보았다. 덱은 배열의 앞과 뒤에 값을 추가하고 삭제할 수 있는 자료구조이다. 큐 풀어보고 난 뒤라 이것도 원형으로 생각하면 배열에서 풀 수 있을 것이라고 생각했다.
덱의 앞에 추가/삭제하기 위한 변수로 front, 덱의 뒤에 추가/삭제하기 위한 변수로 back을 인자로 가지고 있으며, 큐 문제와의 차이점은 두 변수가 모두 순방향/역방향 순회한다는 점이다. 파이썬의 경우 배열의 인덱스에 음수를 넣으면 역방향으로 순회하나 자바는 음수 인덱스를 지원하지 않는다. 따라서 배열의 마지막 인덱스에서 오른쪽으로 한칸 이동할 때는 0을 가리켜야 하고, 배열의 처음 인덱스에서 왼쪽으로 한 칸 이동할 때는 배열의 마지막 인덱스를 가리키는 조건을 추가해주어야 한다.
처음 시도할 때는 front와 back을 모두 0으로 초기화하고 이에 맞는 코드를 작성했는데, 초기 상태에서 값을 추가하면 다른 포인터도 함께 옮겨 주어야 한다. 예를 들어 push_back으로 덱의 뒷부분에 1을 추가한다고 하면, deque[back] = deque[0] = 1 이 되고, push_front 시 값을 덮어씌우지 않도록 front 변수를 왼쪽으로 한칸 옮겨야 한다. 이러한 상황에서 별도로 조건을 추가하면서 코드의 가독성이 많이 떨어졌고, IntelliJ에서는 문제없이 작동했으나 백준에서는 ArrayIndexOfBounds 에러가 발생했다.
이에 대한 해결책으로 처음부터 front는 배열의 마지막값에서 시작하고, back은 0에서 시작하도록 초기화했다. front를 오른쪽으로 한칸 옮겼을 때(+1) back과 위치가 같아진다면 empty 상태이며, front가 배열의 마지막값일 경우를 대비해 front+1을 배열의 길이로 나누어준 값을 back과 비교했다. push는 front의 경우 front 위치에 값을 저장한 뒤 왼쪽으로 한칸 이동(-1), back의 경우 오른쪽으로 한칸 이동(+1)하도록 했고 0과 배열의 마지막 인덱스인 경우 조건을 추가해주었다. pop은 반대로 front의 경우 오른쪽으로 한칸 이동(+1), back의 경우 왼쪽으로 한칸 이동(-1)해 주었고 size는 front가 back보다 큰 경우와 작은 경우를 구분해주어야 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.*;
public class Main {
public static class Deque {
int[] deque;
int front;
int back;
int arrSize;
public Deque(int arrSize) {
this.deque = new int[arrSize];
this.front = arrSize-1;
this.back = 0;
this.arrSize = arrSize;
}
public void push_front(int x) {
deque[front] = x;
if (front==0) front = arrSize-1;
else front--;
}
public void push_back(int x) {
deque[back] = x;
if (back==arrSize-1) back = 0;
else back++;
}
public void pop_front() {
if ((front+1)%arrSize != back) {
if (front == arrSize-1) front=0;
else front++;
System.out.println(deque[front]);
} else System.out.println(-1);
}
public void pop_back() {
if ((front+1)%arrSize != back) {
if (back == 0) back = arrSize-1;
else back--;
System.out.println(deque[back]);
} else System.out.println(-1);
}
public void size() {
if (front<back) {
System.out.println(back-(front+1));
} else {
System.out.println(back + (arrSize-1-front));
}
}
public void empty() {
if ((front+1)%arrSize == back) { //front와 back이 이웃하는 경우
System.out.println(1);
} else System.out.println(0);
}
public void front() {
if ((front+1)%arrSize != back) {
int idx = (front+1)%arrSize;
System.out.println(deque[idx]);
} else System.out.println(-1);
}
public void back() {
if ((front+1)%arrSize != back) {
int idx = (back-1+arrSize)%arrSize;
System.out.println(deque[idx]);
} else System.out.println(-1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Deque deque = new Deque(N);
for(int i=0; i<N; i++) {
String[] cmd = br.readLine().split(" ");
switch (cmd[0]) {
case "push_front":
int x = Integer.parseInt(cmd[1]);
deque.push_front(x);
break;
case "push_back":
int y = Integer.parseInt(cmd[1]);
deque.push_back(y);
break;
case "pop_front":
deque.pop_front();
break;
case "pop_back":
deque.pop_back();
break;
case "empty":
deque.empty();
break;
case "size":
deque.size();
break;
case "front":
deque.front();
break;
case "back":
deque.back();
break;
}
}
}
}
결과는 드디어 성공이었다! 그러나 이 코드는 N번의 명령어를 입력받는 상황에 맞게 구현한 거라 덱의 길이가 N이고, front와 back이 같아지는 지점에 대해 고려하지 않았다. 예를 들어 위의 경우처럼 길이가 3인 q에서 push_back을 3번 수행하는 경우 back은 다시 0을 가리키게 된다. 명령어가 N개로 제한되지 않는다면 의도와는 다르게 배열이 엉망으로 덮어씌워질 것이다.. 또한 자료구조의 핵심인 동적 할당도 고려되지 않은 방식이다. size 함수도 push, pull 마다 size를 카운트해주면 훨씬 간단하게 구할 수 있다.
천재 만재 선생님의 글을 읽으며 또 배워갑니다… 그리고 클래스 내부에 있는 값들은 private으루,,,
배열로 간단하게 문제에 맞춰 구현하는 정도는 해보았으니 다음엔 리스트로 구현해보고 실제 인터페이스가 구현된 라이브러리까지 살펴보아야겠다! 부끄럽고 갈 길이 차암 멀다