자바 - ArrayDeque으로 코테 푸는 법

😉 시작해볼까?!

 

ArrayDeque는 Java의 Deque 인터페이스를 구현한 배열 기반의 더블 엔디드 큐(double-ended queue)입니다. LinkedList와 함께 자바에서 가장 일반적으로 사용되는 덱 구현체 중 하나로, 양쪽 끝에서 요소를 효율적으로 추가하거나 제거할 수 있는 구조입니다. ArrayDeque는 스택이나 큐의 기능을 모두 구현할 수 있어 매우 유연하며, 특히 메모리 사용과 성능 측면에서 많은 장점을 제공합니다.

ArrayDeque의 주요 특징

1. 높은 효율성: ArrayDeque는 내부적으로 동적 배열을 사용하여 요소를 저장합니다. 배열을 사용하기 때문에 메모리 할당이 연속적이며, 요소에 대한 빠른 임의 접근이 가능합니다.
2. 용량 제한 없음: ArrayDeque는 초기 용량을 설정할 수 있지만, 필요에 따라 자동으로 확장됩니다. 이는 LinkedList에 비해 메모리 낭비가 적고, 큐의 크기를 걱정하지 않아도 되는 이점을 제공합니다.
3. Null 값 불허: ArrayDeque는 null 값을 허용하지 않습니다. 요소로 null을 사용하려고 하면 NullPointerException을 던집니다. 이는 null 값을 특정 상황의 유효한 값으로 사용하지 않도록 함으로써, 오류 가능성을 줄여줍니다.

웬만하면 그냥 어레이덱 쓰라는 이유가 있었구만!

주요 메서드

• 추가 및 제거
  • addFirst(E e)와 offerFirst(E e): 덱의 앞쪽에 요소를 추가합니다.
  • addLast(E e)와 offerLast(E e): 덱의 뒤쪽에 요소를 추가합니다.
  • removeFirst()와 pollFirst(): 덱의 앞쪽에서 요소를 제거하고 반환합니다.
  • removeLast()와 pollLast(): 덱의 뒤쪽에서 요소를 제거하고 반환합니다.
• 검사
  • getFirst()와 peekFirst(): 덱의 첫 번째 요소를 조회합니다.
  • getLast()와 peekLast(): 덱의 마지막 요소를 조회합니다.
• 기타 유용한 메서드
  • clear(): 덱의 모든 요소를 제거합니다.
  • size(): 덱에 있는 요소의 수를 반환합니다.
  • isEmpty(): 덱이 비어 있는지 확인합니다.

그냥 뭐... 큐-덱 인터페이스를 충실히 구현했군요!

import java.util.ArrayDeque;
import java.util.Deque;

public class Example {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        deque.offerFirst(10);
        deque.offerLast(20);
        System.out.println(deque.peekFirst()); // 출력: 10
        System.out.println(deque.peekLast());  // 출력: 20

        deque.pollFirst();
        System.out.println(deque.peekFirst()); // 출력: 20
    }
}

 

사용 시나리오

ArrayDeque는 다음과 같은 상황에서 특히 유용합니다:

• 스택 구현: LIFO(Last-In-First-Out) 연산을 위해 push와 pop 메서드(addFirst, removeFirst)를 사용할 수 있습니다.
• 큐 구현: FIFO(First-In-First-Out) 연산을 위해 offer와 poll 메서드(offerLast, pollFirst)를 사용할 수 있습니다.
• 슬라이딩 윈도우 문제: 양쪽 끝에서 삽입 및 삭제가 필요한 알고리즘 문제에서 ArrayDeque를 활용할 수 있습니다.

ArrayDeque는 내부적으로 동적 배열을 사용하므로 요소의 빠른 삽입 및 삭제가 가능하며, 메모리 사용이 효율적입니다. 스택이나 큐를 포함한 다양한 문제 해결에 적합하므로, 자바에서 데이터 구조를 구현할 때 흔히 사용됩니다.

 

이게 사이즈 제한도 없고 동적 배열이다 보니까 그럼 ArrayList 쓰지 말고 얘를 더 많이 쓸까 싶었다.

그러니까...

 

ArrayDeque와 ArrayList는 비슷해 보일 수 있지만, 각각의 사용 케이스와 성능 특성에 차이가 있어, 특정 상황에 따라 하나가 다른 하나보다 더 적합할 수 있습니다. 각각의 자료구조가 언제 더 나은 선택인지 이해하는 것이 중요합니다.

 

라고 이야기한다.

ArrayDeque의 장점

1. 양쪽 끝에서의 효율적인 연산: ArrayDeque는 양쪽 끝에서 요소를 추가하거나 제거하는 연산을 O(1) 시간 복잡도로 수행할 수 있습니다. 이는 스택 또는 큐 연산에 이상적입니다.
2. 메모리 사용 효율성: ArrayDeque는 사용하지 않는 메모리 공간을 최소화합니다. 배열의 크기를 정확하게 조절하여 요소의 추가 및 제거에 따라 동적으로 조절됩니다.
3. Null 값 불허: ArrayDeque는 null 값을 허용하지 않습니다. 이는 실수로 null을 삽입하려는 시도를 방지하고, null 체크 로직을 단순화합니다.

ArrayList의 장점

1. 임의 접근: ArrayList는 인덱스를 통한 빠른 임의 접근(O(1))을 제공합니다. 특정 위치의 요소를 읽거나 변경할 필요가 있을 때 유용합니다.
2. 용이한 요소 추가: 리스트의 끝에 요소를 추가하는 것은 매우 효율적이며(O(1)의 상시복잡도, 아주 드물게 O(n)), 이는 대부분의 사용 케이스에서 큰 장점이 됩니다.
3. API 호환성: 많은 Java 라이브러리와 프레임워크가 List 인터페이스를 기대하기 때문에 ArrayList는 API와의 호환성 측면에서 유리할 수 있습니다.

언제 ArrayDeque를 사용하는 것이 더 나은가?

• 양쪽 끝에서 요소를 추가하거나 제거하는 작업이 빈번할 때
• 스택이나 큐의 기능이 필요할 때
• null 값을 요소로 허용하지 않아야 할 때

언제 ArrayList를 사용하는 것이 더 나은가?

• 리스트 중간에 접근하거나 수정하는 작업이 자주 필요할 때
• 데이터를 순차적으로 처리하면서 간혹 요소를 임의로 접근할 필요가 있을 때
• 외부 API와의 호환성이 중요할 때

결국 선택은 특정 애플리케이션의 요구 사항과 성능 요구 사항에 따라 달라집니다. 각 자료 구조의 특성을 이해하고 그에 따라 가장 적합한 도구를 선택하는 것이 중요합니다.

 

인덱스 써야 하면 ArrayList, 그 외 상황에서는 그냥 ArrayDeque 써도 별 문제 없겠단 생각이 든다.

---

바로 문제 들어간다.

 

... 그런데 GPT가 또 슬라이딩 윈도우 최대값 문제를 뱉었다.

이해는 한다. 전의 문제는 Queue로 구현한 LinkedList로 풀기 좋은 문제였는데...

덱이 큐를 구현했다 보니... 어쩔 수 없네.

그냥 눈으로만 한 번 보자! 

 

ArrayDeque를 활용하여 효율적으로 해결할 수 있는 대표적인 코딩 문제는 "슬라이딩 윈도우 최대값" 문제입니다. 이 문제는 ArrayDeque의 양방향 접근성과 효율적인 요소 추가 및 제거 기능을 활용하여 효과적으로 해결할 수 있습니다.

문제: 슬라이딩 윈도우 최대값

문제 설명: 정수 배열 nums와 크기 k의 슬라이딩 윈도우가 주어집니다. 슬라이딩 윈도우는 배열의 첫 요소부터 시작하여 k만큼의 길이로 한 칸씩 오른쪽으로 이동합니다. 각 슬라이딩 윈도우 위치에서의 최대값을 계산하여 배열로 반환하세요.

 

예시:

• 입력: nums = [1,3,-1,-3,5,3,6,7], k = 3
• 출력: [3,3,5,5,6,7]

최적의 솔루션

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            // Remove elements not within the window
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            
            // Remove smaller numbers in k range as they are useless
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            // Add current value at the end of the deque
            deque.offer(i);
            
            // Window starts from i = k - 1
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        
        return result;
    }
}

 

덱을 구현한 링크드리스트로 푸나 어레이덱으로 푸나 정말 똑같구만. 🥲

 

그래도

이 문제에서 ArrayDeque를 사용하는 이유는 덱에서 제공하는 빠른 양방향 삽입 및 삭제 기능 덕분에 요소를 효율적으로 관리할 수 있기 때문입니다. 또한, ArrayDeque는 내부적으로 배열을 사용하여 요소를 관리하므로, LinkedList보다 메모리 사용면에서 더 효율적일 수 있습니다.