Java Dequeue

* Dequeue 

Dequeue deck이라고 발음하기도 하는데, 양 끝이 열려있는 통로처럼 생긴 자료구조이다.
양 끝이 열려 있어 dequeue에 저장되어 있는 데이터들은 head와 tail 양 쪽에서 꺼내고 넣을 수 있는 특징이 있다.

참조: Dequeue API



 아래는 Hackerrank java Dequeue문제이다. 
n개의 int 값이 주어지며, 그 데이터들의 서브 배열의 길이는 m이다. m개의 서브 배열을 만들어가면서 서브 배열들 속에서 유니크한 데이터들의 수의 최대값을 구하는 문제이다.  


입력 예시)
6  =>n
3  => m
5 3 5 2 3 2 =>n개의 데이터

1번째 subArray: [5, 3, 5] - 유니크 데이터 개수: 2
2번째 subArray: [3, 5, 2] - 유니크 데이터 개수: 3
3번째 subArray: [5, 2, 3] - 유니크 데이터 개수: 3
4번째 subArray: [2, 3, 2] - 유니크 데이터 개수: 2

최대값은 3이 된다.

import java.util.*;
    public class test {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Deque deque = new ArrayDeque();
            int n = in.nextInt();
            int m = in.nextInt();

            int max = 0;
            Set set = new HashSet(); //유니크한 데이터만 저장하기 위한 HashSet

            for (int i = 0; i < n; i++) {
                int num = in.nextInt();
                deque.add(num); //dequeue에 값을 넣으면서
                set.add(num); //set에도 값을 넣는다.
                if(deque.size() == m){ //서브배열만큼 넣었을 때
                    if(max < set.size()){ 
                        max = set.size();
                    }
                    int first = deque.removeFirst(); //dequeue에서 첫번째 데이터를 지우고 그 값 저장한다.
                    if(!deque.contains(first)) set.remove(first); //point

                }
            }
            
            System.out.println(max);

        }
    }

포인트는 이 부분이다.

if(!deque.contains(first)) set.remove(first); 

dequeue에 first 값이 존재하지 않는다면, 그 값을 set에서 삭제한다.
dequeue에 첫 번째 값이 존재하지 않는다는 말은 first 값과 중복 된 값이 없다는 뜻이다. 
 즉 중복된 값이 없으므로 set 집합에서도 지워주어야 한다.
first 값을 삭제하고 난 후에도 first 값이 dequeue 안에 또 존재한다면, set에서는 삭제 처리를 하지 않아도 된다. 
set은 유니크한 데이터만 존재하므로 first 값이 이미 삭제 된 것이나 마찬가지이기 때문이다.