[TIL] Deque 자료구조

*20230111의 회고

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120844

프로그래머스

   위의 링크는 오늘 알고리즘 문제 스터디를 하면서 풀었던 문제다. direction 이 "right" 이면 주어진 배열의 원소를 오른쪽으로 한칸씩 이동시키는 것이고, "left" 이면 주어진 배열의 원소를 왼쪽으로 한칸씩 이동시킨 배열을 출력해주는 문제이다.

우선 나의 풀이를 먼저 첨부하자면, 이렇다.

public static int[] solution(int[] numbers, String direction) {
    int[] answer = new int[numbers.length];

    if(direction.equals("right")) {
        answer[0] = numbers[numbers.length-1];
        for(int i = 1; i < numbers.length; i++) {
            answer[i] = numbers[i - 1];
        }
    }
    else {
        answer[answer.length-1] = numbers[0];
        for(int i = 0; i < answer.length-1; i++) {
            answer[i] = numbers[i + 1];
        }
    }

    return answer;
}

   인덱스의 범위를 벗어나지 않도록 첫번째 원소와 마지막 원소를 바꾸는 부분을 따로 처리해주고, 나머지 원소는 한칸씩 이동시키는 과정을 for 문을 통해서 진행하였다. 그런데 스터디원분들 중에서 Deque 라는 자료구조를 통해서 푸신 분이 계셔서 이 부분이 낯설고 괜찮았었다. 그래서 Deque에 대해 정리해보려 한다.

 

Deque(Double - Ended Queue)

• 원래 큐는 데이터가 한방향으로 들어와서 한방향으로 나가는 자료구조이다(First In, First Out).
• Deque(데크) 는 데이터가 양쪽 방향 모두 들어왔다 나갈 수 있는 자료구조이다. 
• addFirst() : 데크 앞쪽에 원소를 삽입, 용량 제한이 있는 데크의 경우 예외가 발생.
• offerFirst() : 데크 앞쪽에 원소를 삽입, 용량 제한이 있는 데크의 경우 false 를 리턴.
• addLast(), add() : 데크의 마지막에 원소를 삽입, 용량 제한이 있는 데크의 경우 예외가 발생.
• offerLast() : 데크의 마지막에 원소를 삽입, 용량 제한이 있는 데크의 경우 false 를 리턴.
• removeFirst(), remove() : 데크의 앞쪽의 원소를 뽑아서 리턴. 데크가 비어있는 경우 예외가 발생.
• pollFirst(), poll() : 데크의 앞쪽의 원소를 뽑아서 리턴, 데크가 비어있는 경우 null 을 리턴.
• removeLast() : 데크의 마지막 원소를 뽑아서 리턴, 데크가 비어있는 경우 예외가 발생.
• pollLast() : 데크의 마지막 원소를 뽑아서 리턴, 데크가 비어있는 경우 null 을 리턴.

 

아래는 Deque 를 이용해서 다시 풀어본 코드이다.

 public static ArrayDeque<Integer> solution(int[] numbers, String direction) {
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    for(int x : numbers) {
        deque.add(x); //numbers 의 원소를 모두 deque 에 넣어줌
    }
    if (direction.equals("right")) {
        deque.addFirst(deque.removeLast()); //deque의 가장 마지막 원소를 빼서 제일 앞에 넣어줌
    }
    else {
        deque.addLast(deque.removeFirst()); //deque의 가장 처음 원소를 빼서 마지막에 넣어줌
    }
    return deque;
}

   이렇게 deque 를 이용해서 더 간단하게 문제를 풀 수 있었다. 같은 문제를 여러가지 방면으로 생각할 수 있게 되어서 스터디를 하길 정말 잘했다는 생각이 든다!! 덕분에 오늘 새로운 자료구조를 이용해서 문제를 풀어볼 수 있었다. 오늘의 회고 끝 ~!