큐(Queue)
Queue의 사전적 정의는 줄이다.
줄 하고 생각하면 줄을 서서 입장을 한다던가, 줄을 서서 구매를 하는 모습을 떠올릴 수 있다.
자료구조인 Queue 역시 이와 같다.
실생활에서의 줄과 자료구조 큐는 전부 먼저 줄을 선 사람이 먼저 목적을 달성하는 것이다.
이런 특징을 선입선출, 영어로는 First In First Out이라 하여 줄여서 FIFO라고 한다.
자료구조 큐(Queue)
자료구조로서의 큐는 앞서 말했듯 줄을 서는 행위와, 목적을 달성하는 행위가 있다. 이때 목적을 달성하는 행위는 줄을 선 데이터가 줄에서 빠져 나오는 것을 말한다.
여기서 줄을 서는 행위는 enqueue, 줄에서 나오는 행위는 dequeue라고 부른다.
시간 복잡도
큐에서 사용할 수 있는 명령 중 enqueue, dequeue, 그리고 검색에 관한 시간 복잡도이다.
| 명령 | 시간복잡도 |
|---|---|
| enqueue | O(1) |
| dequeue | O(1) |
| search | O(n) |
연습문제 백준 1021
큐와 관련된 연습 문제 백준의 1021번 회전하는 큐 문제이다.
이 문제는 주어진 N이하의 정렬된 자연수가 담긴 양방향 순환 큐에서 1, 2, 3번 연산을 수행하며 원하는 수를 출력하고, 2번과 3번 연산을 사용한 최소값을 출력하는 문제이다.
접근
원소를 뽑아내는 것은 문제가 되지 않고, 관건은 2번 연산을 하는 것과 3번 연산을 하는 것 중 어떤 것이 이득인지를 계산해야 한다고 생각했다.
아래 그림을 보면 녹색 원인 1번에서 2번으로 가기 위해선 2번 연산을 사용하는 것이 좋지만 5번으로 가기 위해선 3번 연산을 활용하는 방안이 좋다.
그럼 이 케이스를 두고 모든 상황에서 활용할 수 있는 식으로 만들어야 한다.
그 식은 두개에서 나올 수 있는 케이스 중 더 작은 케이스를 사용하는 것이었다.
식은 아래와 같이 세웠다.
이동 횟수 = min(목표 인덱스 - 현재 인덱스 , 전체 사이즈 - 목표 인덱스 + 현재 인덱스)
이렇게 할 경우 1과 5의 경우엔 (4-0) vs (5-4) = 1 로 1칸만 이동하는 게 더 좋다는 것을.
1과 2의 경우엔 (1-0) vs (5-1) = 1 칸만 이동한다는 것이 좋다는 것을 알았다.
하지만 이 식을 사용하는 경우엔 어느 방향으로 이동하는 지는 알 수 없지만, 그래도 중요한 건 총 이동 회수이고, 2번이던 3번이던 더 조금 움직일 수 있는 방법을 선택한 것이니 사용해도 좋다고 생각했다.
이를 활용해서 문제를 풀어 보았다.
코드
최소 거리 구하기 관련 코드이다.
private int rotate(List<Integer> list , int curIdx, int targetIdx){
int left = list.size() - targetIdx + curIdx;
if(curIdx > targetIdx)
left = targetIdx+ (list.size() - curIdx);
return Math.min(Math.abs(targetIdx - curIdx), left);
}값을 빼는 코드이다.
LinkedList를 활용해서 구현하였으며, 해당 인덱스의 위치를 구하고 식에 넣어 회전시킨 수를 더해주었다.
이때 가장 마지막 위치가 삭제될 경우 인덱스를 0으로 해주었다. (본래 인덱스의 우측 값이 기준이 되어야 하기 때문에)
private void dequeue(List<Integer> list , int[] array){
int currentIdx = 0;
int totalRotateCount = 0;
for (int i : array) {
Integer value = i;
int targetIdx = list.indexOf(value);
totalRotateCount += rotate(list,currentIdx,targetIdx);
currentIdx = targetIdx;
list.remove(value);
if(currentIdx == list.size())
currentIdx = 0;
}
System.out.println(totalRotateCount);
}
다른 풀이
사실 이 문제를 이미 풀어본 적 있어서 전과는 다른 풀이로 풀어보고 싶었는데 이전에 풀었던 방법이 좀 더 편해보이긴 한다.
인덱스를 0으로 고정시키고 목표의 인덱스가 절반 이상이면 3번 연산을, 절반 이하면 2번 연산을 하는 방식으로 구현됐다.
하지만 2번과 3번 연산을 반복해서 하는 점이 마음에 안들었나보다.
for (int j = 0; j < target; j++) {
String t = arrays[j];
if (t.equals(c.peek())) {
c.poll();
continue;
}
int index = c.indexOf(t);
int containerSize = c.size();
int half = containerSize / 2;
if (index <= half) {
// left
while (true) {
count++;
c.add(c.poll());
if (t.equals(c.peek())) {
c.poll();
break;
}
}
}else{
// right
while (true) {
count++;
c.addFirst(c.pollLast());
if (t.equals(c.peek())) {
c.poll();
break;
}
}
}
}
결과
![[Pasted image 20230314152158.png]]
두 방법 모두 통과는 한 모습이다. 하지만 두번째 방법은 실제로 넣고 빼고 하는 과정에서 좀 더 시간이 걸렸나보다.
1021번 전체 코드
방법 1
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public void solution() throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
int[] targetArray = new int[k];
st = new StringTokenizer(br.readLine());
int idx = 0;
while(st.hasMoreTokens())
targetArray[idx++] = Integer.parseInt(st.nextToken());
dequeue(list,targetArray);
}
private void dequeue(List<Integer> list , int[] array){
int currentIdx = 0;
int totalRotateCount = 0;
for (int i : array) {
Integer value = i;
int targetIdx = list.indexOf(value);
totalRotateCount += rotate(list,currentIdx,targetIdx);
currentIdx = targetIdx;
list.remove(value);
if(currentIdx == list.size())
currentIdx = 0;
}
System.out.println(totalRotateCount);
}
private int rotate(List<Integer> list , int curIdx, int targetIdx){
int left = list.size() - targetIdx + curIdx;
if(curIdx > targetIdx)
left = targetIdx+ (list.size() - curIdx);
return Math.min(Math.abs(targetIdx - curIdx), left);
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}방법 2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class P1021_2 {
StringBuilder sb = new StringBuilder();
LinkedList<String> c = new LinkedList<>();
int count = 0;
int target;
String[] arrays;
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int size = Integer.parseInt(st.nextToken());
target = Integer.parseInt(st.nextToken());
arrays = new String[target];
st = new StringTokenizer(br.readLine());
int i = 0;
for (int j = 1; j <= size; j++) {
c.add(String.valueOf(j));
}
while (st.hasMoreTokens()) {
arrays[i++] = st.nextToken();
}
for (int j = 0; j < target; j++) {
String t = arrays[j];
if (t.equals(c.peek())) {
c.poll();
continue;
}
int index = c.indexOf(t);
int containerSize = c.size();
int half = containerSize / 2;
if (index <= half) {
// left
while (true) {
count++;
c.add(c.poll());
if (t.equals(c.peek())) {
c.poll();
break;
}
}
}else{
// right
while (true) {
count++;
c.addFirst(c.pollLast());
if (t.equals(c.peek())) {
c.poll();
break;
}
}
}
}
System.out.println(count);
}
public static void main(String[] args) throws Exception {
new P1021_2().solution();
}
}