[Baekjoon/Programmers] 10845 큐
10845 큐문제 해결 과정.
이번에는 큐를 직접 구현하는 문제이다. 지난번 스택의 경우는 가장 늦게 들어온 값이 먼저 나가므로 top이라는 변수를 포인터처럼 사용하여 값을 덮어씌울 수 있었는데, 큐같은 경우에는 먼저 들어온 값이 먼저 나가는 구조이기 때문에 고민할 점이 많았다. 가장 처음 들어온 값을 가리키는 bottom 변수와 가장 나중에 들어오는 값이 위치할 곳을 가리키는 top 이라는 변수를 만들어 주었다. 그러나 아래 그림처럼 push와 pop을 반복하면 배열 내 bottom 왼쪽 부분은 비어 있게 되고 오른쪽으로 쏠리는 현상이 나타난다.
정말 단순하게 이런 아이디어밖에 떠오르지 않았고…
- 배열의 길이를 매우 큰 값으로 둔다.
- pop할 때마다 기존의 배열을 복사해 새로운 배열로 만든다.
다른 자료구조를 이용한다.우선 배열로 구현해보자.
둘다 매우 비효율적인 것 같지만 그나마 차악인 2번 아이디어로 시도해 보았다.
queue = Arrays.copyOfRange(queue, bottom, top);
pop의 경우 bottom에 있는 값을 우선 출력하고, bottom+1부터 top까지의 값만 복사하고자 했으나 ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0 경우가 발생해서 배열 복사를 bottom부터 top까지가 아닌 MAX_SIZE까지로 변경해주었다.
최종 코드는 다음과 같다.
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
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static class Queue {
int[] queue;
int top;
int bottom;
int MAX_SIZE = 10_000;
public Queue() {
this.queue = new int[MAX_SIZE];
this.top = 0;
this.bottom = 0;
}
public void push(int x){
queue[top] = x;
top++;
}
public void pop(){
if (top!=bottom) {
System.out.println(queue[bottom]);
bottom++;
queue = Arrays.copyOfRange(queue, bottom, MAX_SIZE);
top --;
bottom--;
} else System.out.println(-1);
}
public void size(){
System.out.println(top);
}
public void empty(){
System.out.println(top==bottom? 1:0);
}
public void front(){
System.out.println(top==bottom? -1:queue[bottom]);
}
public void back() {
System.out.println(top==bottom? -1:queue[top-1]);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue queue = new Queue();
int num = Integer.parseInt(br.readLine());
for(int i=0; i<num; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
switch (cmd) {
case "push":
int x = Integer.parseInt(st.nextToken());
queue.push(x);
break;
case "pop":
queue.pop();
break;
case "size":
queue.size();
break;
case "empty":
queue.empty();
break;
case "front":
queue.front();
break;
case "back":
queue.back();
break;
}
}
}
}
그렇지만 역시나 배열을 매번 복사해 새로 만들어야 한다는 게 썩 마음에 들지 않아 천재만재님들의 코드들을 둘러보다가 https://you88.tistory.com/30 에서 배열로 큐를 구현하고 싶다면 원형 큐를 구현해야 된다는 부분을 읽게 되었다.
원형 큐 아이디어를 보고 구현해 본 큐는 다음과 같다.
배열에서 가장 늦게 들어온 값을 가리키는 front, 가장 먼저 들어온 값을 rear라고 한다. 초기값은 front = 0, rear = -1이며 front = rear + 1 인 경우 배열은 비어있다고 할 수 있다.
push의 경우 queue의 front 인덱스에 값을 넣어주지만, 만약 front가 queue의 크기인 MAX_SIZE와 같아진다면 rare 자리에 값을 넣는다. pop의 경우 배열이 비어있지 않다면 rear++한 뒤 rear에 있는 값을 print 해준다. front가 배열의 끝까지 갈 경우 다시 rear에서 부터 값을 push하게 된다.
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
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static class Queue {
int[] queue;
int front;
int rear;
int MAX_SIZE = 10_000;
public Queue() {
this.queue = new int[MAX_SIZE];
this.front = 0;
this.rear = -1;
}
public void push(int x){
if (front < MAX_SIZE) {
queue[front] = x;
front++;
} else {
queue[rear] = x;
rear++;
}
}
public void pop(){
if (front != rear + 1) {
rear++;
System.out.println(queue[rear]);
} else System.out.println(-1);
}
public void size(){
System.out.println(front-(rear+1));
}
public void empty(){
System.out.println(front == rear + 1 ? 1:0);
}
public void front(){
System.out.println(front == rear + 1 ? -1:queue[rear+1]);
}
public void back() {
System.out.println(front == rear + 1 ? -1:queue[front-1]);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Queue queue = new Queue();
int num = Integer.parseInt(br.readLine());
for(int i=0; i<num; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
switch (cmd) {
case "push":
int x = Integer.parseInt(st.nextToken());
queue.push(x);
break;
case "pop":
queue.pop();
break;
case "size":
queue.size();
break;
case "empty":
queue.empty();
break;
case "front":
queue.front();
break;
case "back":
queue.back();
break;
}
}
}
}
내가 참고한 사이트에서는 front를 나머지 계산으로 해결했고, 여전히 내가 구현한 코드는 찝찝하다.. 백준 문제에서는 N만큼 명령어를 입력하기 때문에 배열의 크기는 N이어도 충분할 것 같아서 수정해주었다.
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
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static class Queue {
int[] queue;
int front;
int rear;
int MAX_SIZE;
public Queue(int MAX_SIZE) {
this.queue = new int[MAX_SIZE];
this.front = 0;
this.rear = -1;
this.MAX_SIZE = MAX_SIZE;
}
public void push(int x){
if (front < MAX_SIZE) {
queue[front] = x;
front++;
} else {
queue[rear] = x;
rear++;
}
}
public void pop(){
if (front != rear + 1) {
rear++;
System.out.println(queue[rear]);
} else System.out.println(-1);
}
public void size(){
System.out.println(front-(rear+1));
}
public void empty(){
System.out.println(front == rear + 1 ? 1:0);
}
public void front(){
System.out.println(front == rear + 1 ? -1:queue[rear+1]);
}
public void back() {
System.out.println(front == rear + 1 ? -1:queue[front-1]);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
Queue queue = new Queue(num);
for(int i=0; i<num; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
switch (cmd) {
case "push":
int x = Integer.parseInt(st.nextToken());
queue.push(x);
break;
case "pop":
queue.pop();
break;
case "size":
queue.size();
break;
case "empty":
queue.empty();
break;
case "front":
queue.front();
break;
case "back":
queue.back();
break;
}
}
}
}
This post is licensed under CC BY 4.0 by the author.