[Java] 백준(실버-4) 10845번 - 큐
문제 풀이
이번 문제는 Queue를 활용하는데, 일반적으로 Queue 인터페이스를 LinkedList로 구현하는 방식이 아닌 Deque와 LinkedList를 활용해 풀어보았다.
Deque 인터페이스나 LinkedList 라이브러리는 앞에서 말한 일반적인 Queue 구현 방식보다 맨 앞과 맨 뒤의 값을 쉽게 가져올 수 있기 때문에 별도로 맨 뒤(back) 값을 구할 필요가 없다.
또한, 백준 10845번 문제와 로직 자체는 비슷한 방식으로 풀 수 있음을 참고하자.
문제를 풀기에 앞서 Deque가 무엇인지 알아보자.
Deque란?
Deque란 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미한다.
덱(Deque)은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다.
특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다.
Deque를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.
아이디어 도출
N개의 명령어를 입력받으며 다음을 수행한다.
- push [N] 명령어를 받으면 N을 큐에 삽입한다.
- pop 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 front(맨 앞값)를 추출하고 출력한다.
- size 명령어를 받으면 현재 큐의 삽입된 값의 개수를 출력한다.
- empty 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “1”, 비어있지 않다면 “0”을 출력한다.
- front 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 getFirst() 메서드를 이용해 현재 큐의 front(맨 앞) 값을 출력한다.
- back 명령어를 받으면 큐가 비어있는지 확인하고 비어있다면 “-1”, 비어있지 않다면 getLast() 메서드를 이용해 back(맨 뒤) 값을 출력**한다.
문제에 활용할 Deque는 LinkedList와 동일하게 맨 앞과 맨 뒤 값에 접근이 가능하다.
작성한 코드의 구조는 큐 2 문제와 대부분 동일하다.
Deque와 LinkedList에서 맨 앞값과 맨 뒤값을 구할 때 활용한 getFirst()와 getLast() 메서드를 중점으로 보면 된다.
두가지 방식으로 작성한 코드는 하단에서 확인할 수 있다.
작성코드
작성코드 - Deque 활용
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
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
Deque<Integer> deq = new ArrayDeque();
for(int i=0; i<N; i++) {
String cmd = br.readLine();
if(cmd.contains("push")) {
int num = Integer.parseInt(cmd.split(" ")[1]);
deq.offer(num);
}
else {
switch(cmd) {
case "pop":
if(deq.isEmpty()) bw.write("-1"+"\n");
else {
bw.write(deq.poll()+"\n");
}
break;
case "size":
bw.write(deq.size()+"\n");
break;
case "empty":
if(deq.isEmpty()) bw.write("1"+"\n");
else bw.write("0"+"\n");
break;
case "front":
if(deq.isEmpty()) bw.write("-1"+"\n");
else bw.write(deq.peekFirst()+"\n");
break;
case "back":
if(deq.isEmpty()) bw.write("-1"+"\n");
else bw.write(deq.getLast()+"\n");
break;
default:
break;
}
}
}
bw.flush();
bw.close();
br.close();
}
}
작성코드 - LinkedList 인터페이스 활용
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
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
LinkedList<Integer> list = new LinkedList<>();
for(int i=0; i<N; i++) {
String cmd = br.readLine();
if(cmd.contains("push")) {
int num = Integer.parseInt(cmd.split(" ")[1]);
list.add(num);
}
else {
switch(cmd) {
case "pop":
if(list.isEmpty()) bw.write("-1"+"\n");
else {
bw.write(list.removeFirst()+"\n");
}
break;
case "size":
bw.write(list.size()+"\n");
break;
case "empty":
if(list.isEmpty()) bw.write("1"+"\n");
else bw.write("0"+"\n");
break;
case "front":
if(list.isEmpty()) bw.write("-1"+"\n");
else bw.write(list.getFirst()+"\n");
break;
case "back":
if(list.isEmpty()) bw.write("-1"+"\n");
else bw.write(list.getLast()+"\n");
break;
default:
break;
}
}
}
bw.flush();
bw.close();
br.close();
}
}
회고
- 이전에 풀어봤던 큐 2 문제와 거의 비슷한 문제이기에 같은 방식이 아닌 맨 뒤값을 제공해주는 Deque, LinkedList를 활용하는 방식으로 풀어보았다.
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.