Queue
Queue란?
- 데이터를 선입선출(FIFO, First-In-First-Out)의 원칙으로 처리하기 위한 자료구조이다.(ex: 대기열, 순서대로입장, 선착순 등)
Queue의 특징
-
삽입(enqueue)과 삭제(dequeue)가 각각 다른 쪽에서 이루어지는 구조이다.
-
가장 먼저 삽입된 데이터부터 삭제된다.
-
큐의 크기는 동적으로 변경 가능하다.
- 그래프 알고리즘: BFS(Breadth-First Search)에서 사용된다. 꼭꼭!! 이해하고 넘어가야한다.
Queue의 종류
-
일반적인 Queue
-
우선순위 Queue: 우선순위가 높은 데이터를 먼저 처리하는 큐
-
환형 Queue: 큐의 뒤와 앞이 이어져 있는 구조
Queue의 시간 복잡도
-
삽입(enqueue): O(1)
-
삭제(dequeue): O(1)
-
탐색(front, rear): O(1)
Queue와 Stack의 차이점
-
데이터 삽입/삭제 방향의 차이: Queue는 뒤에서 삽입, 앞에서 삭제. Stack 뒤에서 삽입, 뒤에서 삭제한다.
-
데이터 접근 방향의 차이: Queue는 처음과 끝에서 모두 접근 가능. Stack은 끝에서만 접근 가능하다.
Queue의 활용 방법 및 주의할 점
-
대기열, 그래프 알고리즘 등 다양한 분야에서 활용된다.
-
삽입과 삭제가 각각 다른 쪽에서 이루어지므로, 삽입된 데이터를 모두 삭제하지 않고 일부만 삭제하는 등의 작업이 어려움이 있다.
-
크기가 동적으로 변경 가능하므로, 큐의 최대 크기를 초과하지 않도록 주의해야 한다.
Queue의 장단점, 주의할 점
-
장점: 데이터 처리의 선입선출 구조를 갖고 있어, 다양한 분야에서 활용 가능하다.
-
단점: 단점: 중간에 삽입된 데이터를 삭제하는 것이 어렵고, 큐의 최대 크기를 초과하면 데이터를 삽입할 수 없다.
-
배열을 이용한 구현 방법에서 크기가 고정되어 있으므로, 메모리 낭비가 발생할 수 있다.
-
큐의 구현 방법에 따라 삽입, 삭제, 탐색 연산의 시간 복잡도가 달라질 수 있다.
예제문제
문제 : 회전하는 큐 (백준 1021번)
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
10 3
1 2 3
예제 출력 1
0
예제 입력 2
10 3
2 9 5
예제 출력 2
8
예제 입력 3
32 6
27 16 30 11 6 23
예제 출력 3
59
예제 입력 4
10 10
1 6 3 2 7 9 8 4 10 5
예제 출력 4
14
나의 생각, 목표
- 속도향상을 위해, Scanner말고 BufferedReader로 입력을 받아보자.
- StringTokenizer을 사용하여 입력받은 값들을 관리해보자.
- 오른쪽, 왼쪽 이동할 기준을 정해야한다.
- 이동할 때마다, count+=1한다.
- 이동할 기준 : queue에 절반값의 보다 목표숫자(찾아서 삭제할 값)의 인덱스가 같거나 작으면 왼쪽으로 이동, 아니면 오른쪽으로 이동시킨다.
- 원하는 값이 나올때 까지 반복한다.
- 계산이 끝나면 값 삭제하고 다음 찾을 값을 받아온다.
구현
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Queue01 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");// " ", 기준으로 토큰화해서 관리할 수 있다. ex : 입력값 10 3
int size = Integer.parseInt(st.nextToken()); // 데이터를 읽고 int형으로 바꾼다. 첫번째 토큰값 10
int n = Integer.parseInt(st.nextToken()); // 다음 토큰값 3
ArrayList<Integer> numbers = new ArrayList<>(); //n개의 찾을값을 저장할 리스트
st = new StringTokenizer(bf.readLine(), " ");
for (int i = 0; i < n; i++) {
numbers.add(Integer.valueOf(st.nextToken())); // 위와 같이 토큰으로 나눠서 순서대로 넣어준다.
}
ArrayList<Integer> queue = new ArrayList<>(); // size만큼의 리스트, 이 코드에서는 queue처럼 동작시킬 것이다.
queue.addAll(IntStream.rangeClosed(1, size).mapToObj(Integer::valueOf).collect(Collectors.toList())); // queue에 1부터 size까지 수열을 넣어준다. (ex:1, 2, 3 ... size)
int cnt = 0; // 이동한 횟수를 저장할 count변수, 0으로 초기화
for (int j = 0; j < numbers.size(); j++) // 찾을 값만큼 반복한다. (ex:찾을값이 2,9,5 이면 3번 반복)
{
if (queue.indexOf(numbers.get(j)) <= queue.size() / 2) // 찾을값의 인덱스가 queue사이즈/2보다 작거나 같으면 왼쪽으로 이동하는게 더 빠르다.
{
for (int i = 0; i < queue.size() / 2; i++) // queue사이즈에 반만큼만 반복한다.
{
if (queue.get(0) == numbers.get(j)) { // 만약, 찾는 값이 나왔다면 break)
break;
}
Collections.rotate(queue, -1); // 찾는 값이 아니면 왼쪽으로 한칸 이동
cnt++; // 이동한 횟수 +=1
}
} else {
for (int i = 0; i < queue.size() / 2; i++) // 오른쪽으로 이동할 경우
{
if (queue.get(0) == numbers.get(j)) { // 만약, 찾는 값이 나왔다면 break)
break;
}
Collections.rotate(queue, 1); // 찾는 값이 아니면 오른쪽으로 한칸 이동
cnt++; // 이동한 횟수 +=1
}
}
queue.remove(0); // 맨앞에 있는값(찾는 값) 삭제
}
System.out.println(cnt); // 이동한 횟수 출력
}
}
마무리 및 고찰
- java11 에서는 stream에서 toList()가 불가했다.
- toList()를 collect(Collectors.toList())로 변경하였다.
- Java16부터 stream에서 toList를 다이렉트로 사용할 수 있다.
- 이 문제에서 고민은 오른쪽, 왼쪽 둘 중 어디로 이동할거냐이다.
- 이유는 위치에 따라, 소모되는 이동횟수가 다르기 때문이다.
- 결국 두 이동값 중, 작은 값 만큼 이동하면 정답이다.
- Math.min(오른쪽,왼쪽)이 이동한 최소값이다.
- 출발지는 변수로 변경해주면 된다.
- 왼쪽이동은 : 출발인덱스(now)에서 목표인덱스(goal)를 뺀, 절대값이 그 거리(gap)이다.
- 오른쪽 이동은 : 반대로 이동하는 거니까, queue사이즈에서 gap만큼 뺀값이다.
[설명 예시]
list로 만든 queue : [1,2,3,4,5] (인덱스 0번부터 4번까지)
큐의 사이즈 : 5
출발위치(now) : 당연히 0번인덱스 부터
찾을 값 : 3 (인덱스 2번위치(goal==2)에 있다.)
알고리즘 ->
왼쪽으로 이동해야하는 횟수 : |0-2| = 2칸 (출발인덱스에서 찾을값의 인덱스 뺀 값)
오른쪽으로 이동해야하는 횟수 : 반대로 이동하는 거니까 queue사이즈에서 위의 값을 뺀값 == 5-2 == 3칸
둘 중 뭐가 적게 이동하니? => Math.min(왼쪽:2, 오른쪽:3) == 왼쪽! == 2!
그러면 왼쪽값만큼 이동횟수 카운트해줘 => cnt+=2
이제 찾았으니까, 값 3 삭제해줘 remove(goal)
출발위치 0에서, goal부터 시작하게끔 바꾸자 => now=goal
바로 해보자
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Queue02 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int size = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] input = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
int result = solution(size, n, input);
System.out.println(result);
}
public static int solution(int size, int n, int[] input) {
List<Integer> queue = new ArrayList<>(IntStream.rangeClosed(1, size).boxed().collect(Collectors.toList()));
int now = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
int goal = queue.indexOf(input[i]); // 찾을 값의 인뎃스
int gap = Math.abs(goal - now); // 왼쪽으로 이동거리
cnt += Math.min(gap, queue.size() - gap); // (왼쪽 vs 오른쪽)
queue.remove(goal); // 찾은값 제거
now = goal; // 출발지점 초기화
}
return cnt;
}
}
여러 접근법으로 문제를 풀어보았다! 코드가 훨씬 간결해졌지만, 속도향상은 적었다. Deque을 사용해서 풀어보자
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int size = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] numbers = Arrays.stream(bf.readLine().split(" "))
.mapToInt(Integer::valueOf)
.toArray();
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 1; i <= size; i++) {
queue.addLast(i);
}
int cnt = 0;
for (int j = 0; j < numbers.length; j++) {
int targetIndex = -1;
for (int i = 0; i < queue.size(); i++) {
if (queue.toArray()[i].equals(numbers[j])) {
targetIndex = i;
break;
}
}
int mid = queue.size() / 2;
if (targetIndex <= mid) {
for (int i = 0; i < targetIndex; i++) {
int temp = queue.removeFirst();
queue.addLast(temp);
cnt++;
}
} else {
for (int i = 0; i < queue.size() - targetIndex; i++) {
int temp = queue.removeLast();
queue.addFirst(temp);
cnt++;
}
}
queue.removeFirst();
}
System.out.println(cnt);
}
}
가독성을 높여보자
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Queue01 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int size = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
List<Integer> numbers = Arrays.stream(bf.readLine().split(" "))
.boxed()
.collect(Collectors.toList());
List<Integer> queue = IntStream.rangeClosed(1, size)
.boxed()
.collect(Collectors.toList());
int cnt = 0;
for (int j = 0; j < numbers.size(); j++) {
int targetIndex = queue.indexOf(numbers.get(j));
int mid = queue.size() / 2;
boolean isLeft = targetIndex <= mid;
for (int i = 0; i < mid; i++) {
if (queue.get(0) == numbers.get(j)) {
break;
}
Collections.rotate(queue, isLeft ? -1 : 1);
cnt++;
}
queue.remove(0);
}
bw.write(String.valueOf(cnt));
bw.flush();
bw.close();
}
}
변수명을 고치고, Stream, BufferedWriter, boolean형을 사용해봤다.
