[JAVA] Deque (덱) (백준 2164)

Deque (덱)

Double-Ended Queue의 약어로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다. 이는 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있다. 따라서 선입선출(FIFO)과 후입선출(LIFO) 개념이 모두 적용될 수 있다.

Java에서 덱은 java.util 인터페이스를 이용해 구현할 수 있다.

주요 메서드

1. 삽입 메서드
• addFirst(element) : 덱의 맨 앞에 요소를 추가
• addLast(element) : 덱의 맨 뒤에 요소를 추가
2. 삭제 메서드
• removeFirst() : 덱의 맨 앞에 있는 요소를 제거하고 반환
• removeLast() : 덱의 맨 뒤에 있는 요소를 제거하고 반환
3. 조회 메서드
• getFirst() : 덱의 맨 앞의 요소를 반환하지만 제거하진 않는다.
• getLast() : 덱의 맨 뒤의 요소를 반환하지만 제거하진 않는다.
4. 기타 메서드
• offerFirst(element) : 덱의 맨 앞에 요소를 추가한다. 큐가 꽉 차있을 경우 예외를 던지지 않고, false를 반환한다.
• offerLast(element) : 덱의 맨 뒤에 요소를 추가한다. 큐가 꽉 차있을 경우 예외를 던지지 않고 false를 반환한다.
• pollFirst() : 덱의 맨 앞의 요소를 제거하고 반환한다. 덱이 비어있으면 null을 반환한다.
• pollLast() : 덱의 맨 뒤에 있는 요소를 제거하고 반환한다. 덱이 비어있으면 null을 반환한다.

예시 1. 회문(palindrome) 여부 판별
회문은 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열을 의미한다. Deque를 사용하여 문자열을 앞뒤로 모두 비교하면서 회문 여부를 판별할 수 있다.

import java.util.Deque;
import java.util.LinkedList;

public class PalindromeChecker {
    public static boolean isPalindrome(String str) {
        // 덱 생성
        Deque<Character> deque = new LinkedList<>();

        // 문자열을 덱에 추가
        for (char c : str.toCharArray()) {
            deque.addLast(c);
        }

        // 앞뒤로 비교하면서 회문 여부 판별
        while (deque.size() > 1) {
            char first = deque.removeFirst();
            char last = deque.removeLast();

            if (first != last) {
                return false; // 회문이 아님
            }
        }

        return true; // 회문임
    }

    public static void main(String[] args) {
        String palindromeStr = "radar";
        String nonPalindromeStr = "hello";

        System.out.println(palindromeStr + " is a palindrome: " + isPalindrome(palindromeStr));
        System.out.println(nonPalindromeStr + " is a palindrome: " + isPalindrome(nonPalindromeStr));
    }
}

2. 최대값이나 최솟값 찾기 (슬라이딩 윈도우)

import java.util.Deque;
import java.util.LinkedList;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        int ri = 0;

        // 인덱스를 저장하는 덱
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            // 현재 윈도우에서 벗어난 인덱스 제거
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // 현재 값보다 작은 값들은 제거
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 현재 인덱스 추가
            deque.offer(i);

            // 결과 배열에 최대값 추가
            if (i >= k - 1) {
                result[ri++] = nums[deque.peek()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);

        System.out.print("Maximum values in sliding windows: ");
        for (int val : result) {
            System.out.print(val + " ");
        }
    }
}

이를 이용해 백준 알고리즘 중 2164 카드 2를 풀어보았다.

백준 2164. 카드 2

백준 2164 카드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> dq = new ArrayDeque<>();

        int N = Integer.parseInt(br.readLine());

        for(int i = N; i >= 1; i--){
            dq.offer(i);
        }

        while(dq.size() > 1){
            dq.pollLast();  //가장 위에 있는 카드를 버림
            int last = dq.pollLast();    //버린 카드 중 가장 위에 있는 카드를
            dq.addFirst(last);  //가장 밑으로 내린다
        }
        
        System.out.print(dq.getFirst());

    }
}