[BOJ - JAVA] 1021 - 회전하는 큐 (덱)

# 주소

https://www.acmicpc.net/problem/1021

1021번: 회전하는 큐

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int count = 0;
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1; i <= n; i++)
            list.add(i);
        while(m-- > 0){
            int num = scan.nextInt();
            while(true){
                if(list.getFirst() == num){
                    list.pollFirst();
                    break;
                }
                if(list.indexOf(num) <= list.size() / 2)
                    list.addLast(list.pollFirst());
                else
                    list.addFirst(list.pollLast());
                count++;
            }
        }
        System.out.println(count);
    }
}

덱 문제를 가져왔습니다. 

덱(Deque)은 Double-ended queue의 줄임말입니다.

큐는 많이 봐와서 알겠지만 단방향 자료구조이고 단방향 연결리스트와 유사한 메커니즘입니다.

반대로 덱은 양방향 연결리스트와 유사한 메터니즘입니다. 즉, 두 개의 종료지점이 있고 양쪽 방향에서 데이터의 삽입, 삭제가 이루어질 수 있습니다.

그래서 장점이라 하면 스택처럼 사용할 수도 있고 큐처럼 사용할 수 있습니다. 

또한 덱은 삽입, 삭제가 총 12가지가 있습니다.

offer계열과 poll계열의 경우 삽입, 삭제 과정에서 저장공간이 넘치거나 삭제할 원소가 없을 때 특정 값을 반환하지만 add계열과 remove계열의 경우 예외를 던집니다. 

또한 offer(add)는 offerLst(addLast)와 같고 poll(remove)는 pollFirst(removeFIrst)와 같습니다. 

즉, 우리가 구현해야할 것은 총 4가지를 위주로 구현하면 됩니다. 

그외에 쓰인 넛이 peek이 있는데 peek의 경우에도 peekFIrst와 같으며 peekLast도 따로 있습니다.

 

위 사진을 보시면 이해가 상당히 빠르실 겁니다.

 

그럼 이 문제는 어떻게 해결하면 좋을까요??

<예시 1>

덱 : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

뽑을 숫자 : 1, 2, 3

-> 1번 연산을 3번하면 되고 2번 연산과 3번 연산은 하지 않으므로 0을 출력하면 됩니다.

 

 

그럼 코드를 살펴보겠습니다.

먼저 n과 m을 입력받고 LinkedList타입의 list를 선언합니다.(list가 덱)

그리고 list에 1부터 n까지 모두 데이터를 삽입합니다.

이후 while문으로 들어가, m이 0이 될 때까지 횟수를 반복합니다.

그리고 num을 입력 받고, 이 num이 만약 제일 최초에 뽑은 것이 num과 일치하면 list에서 뽑고 while문을 빠져나옵니다. 그렇지만 이렇게 해서 빠져나온 녀석들은 count에 포함시키지 않으므로 그대로 넘어갑니다.

예제를 통해 이해해보겠습니다.

이런 예제가 들어왔다고 하겠습니다.

10 3
2 9 5

그럼 덱에는 1부터 10까지 담기게 되고 m의 값은 3이므로 while문을 3번 실행합니다.

2 9 5가 num이 될 것이고 다시금 while문 안으로 들어가서 이것이 첫 번째 if문을 통해 break 될 때까지 반복해서 수행합니다.

자세히 알아봅시다.

2가 제일 먼저 num이 되었을 때, list.gerFirst() = 1이고 num = 2이므로 서로 다릅니다.

그럼 두 번째 if문으로 가게 되고 이 때 list.indexOf(num) 은 list에서 num의 위치를 묻는 메소드입니다.

num의 위치는 1이잖아요?(index는 0부터 시작하기 때문)

그러므로 list의 indexOf(num) = 1이고 이는 list의 크기 / 2보다 작기 때문에(1 <= 5) list의 제일 마지막에 1를 삽입합니다.(2번 연산) 그리고 나서 count를 증가시킵니다. 

그럼 이 때 덱은 {2, 3, 4, 5, 6, 7, 8, 9, 10, 1}이 삽입되고 count = 1입니다.

그리고 두 번째 과정에서 이 2가 1번 연산 시행에 의해 (list.getFirst() -> 2 == num -> 2) 

list에서 뽑히게 되고 break되어 내재된 while문에서 밖으로 나오게 됩니다.

 

이후 두 번째로 입력된 9를 살펴보겠습니다.

9는 현재 덱에서 중앙보다 뒤에 있기 때문에 3번 연산을 시행하는 것이 좋습니다.

현재 덱의 상황은 {3, 4, 5, 6, 7, 8, 9, 10, 1}이고 3번 연산을 한 번 시행하면 

1 3 4 5 6 7 8 9 10입니다. 그리고 한 번 더 시행하면

10 1 3 4 5 6 7 8 9 입니다.

그리고 또 한 번 더 시행하면 9 10 1 3 4 5 6 7 8입니다. 이 때 1번 연산에 의해 9가 출력되면서

3번 연산은 9를 출력하기 위해 총 3번 시행됩니다. 그러므로 지금까지 count는 총 4겠죠?

마지막으로 5를 볼까요?

현재 덱은 10 1 3 4 5 6 7 8입니다

이 5는 3번연산을 시행하는게 낫겠죠???

그럼 한 번 시행하면 8 10 1 3 4 5 6 7이고 한 번 더 시행하면

7 8 10 1 3 4 5 6 이고 또 한 번 더 시행하면 

7 8 10 1 3 4 5 6이고 또 한 번 더 시행하면

6 7 8 10 1 3 4 5 이고 마지막으로 한 번 더 시행하면

5 6 7 8 10 1 3 4가 되며 마침내 5가 출력되어 count는 4가 증가하고 최종적인 count는 8이 됩니다.

이해하셨나요???

 

단일 방향으로 빠져나가고 삽입하는 것은 큐를 활용하되, 모든 문제를 덱으로 풀어도 상관은 없습니다.

또한 덱은 ArrayDeque와 LinkedList를 이용한 덱 구현이 있습니다.

신기한 점이, 저는 LinkedList를 이용해서 웬만하면 큐와 덱을 구현하는데 실제론 ArrayDeque가 훨씬 더 성능이 좋다고 합니다.

시간복잡도가 특히 ArrayDeque는 O(1)이고 LinkedList의 경우 O(N)이기 때문에 시간 절약면에서 뛰어나다고 하네요.

자세한 것은 여기서 https://big-blog.tistory.com/3901

ArrayDeque가 LinkedList보다 나은 이유

참고하시길 바랍니다. 다음엔 ArrayDeque로 구현해봐야겠습니다.

감사합니다.