[프로그래머스 java] 배열 만들기 4

JAVA의 Stack과 Queue를 ArrayDeque로 써야 하는 이유

특징	Stack (Vector 상속)	Deque (ArrayDeque)
성능	- 크기 자동 확장 시 비효율적 - 메모리 관리에 불리함	- 양쪽 끝에서 효율적으로 요소 추가/제거 - 성능 우수
동기화	- 동기화된 메서드 제공 (멀티스레딩 안전)	- 동기화되지 않음 (성능 최적화)
불필요한 기능	- Vector의 기능 상속 (동적 크기 변경 등)	- 필요한 기능만 제공 (간결한 API)
사용 목적	- 전통적인 스택 자료구조 구현 (간단한 경우 사용 가능)	- 스택과 큐를 모두 구현 가능 - 유연하고 효율적
추천 사용 이유	- 비추천: 성능 저하 및 불필요한 동기화	- 권장: 성능 우수, 명확한 API, 큐와 스택 모두 처리 가능

Stack은 Vector 상속하고 있어서 문제가 있기때문에 Deque인터페이스의 ArrayDeque 구현체를 스택과 큐로 사용하는 것을 권장하고 있다.

ArrayDeque개념

1. 개념

ArrayDeque는 자바에서 제공하는 Deque 인터페이스의 구현체로, 양쪽 끝에서 요소를 효율적으로 추가하거나 제거할 수 있는 자료구조이다.

ArrayDeque는 내부적으로 배열을 사용하여 큐와 스택을 모두 구현할 수 있도록 설계되었다. ArrayDeque는 동기화되지 않으며, LinkedList보다 더 나은 성능을 제공한다.

출처 : java doc - ArrayDeque

2. 자주 사용하는 매서드

메서드	설명	사용 예시
addFirst(E e)	덱의 앞부분에 요소를 추가한다. 공간이 부족하면 자동으로 크기를 늘린다.	deque.addFirst("Apple");
addLast(E e)	덱의 뒷부분에 요소를 추가한다. 공간이 부족하면 자동으로 크기를 늘린다.	deque.addLast("Banana");
removeFirst()	덱의 앞부분에서 요소를 제거하고 반환한다. 덱이 비어 있으면 예외 발생.	String first = deque.removeFirst();
removeLast()	덱의 뒷부분에서 요소를 제거하고 반환한다. 덱이 비어 있으면 예외 발생.	String last = deque.removeLast();
peekFirst()	덱의 앞부분에 있는 요소를 제거하지 않고 반환한다. 덱이 비어 있으면 null.	String firstElement = deque.peekFirst();
peekLast()	덱의 뒷부분에 있는 요소를 제거하지 않고 반환한다. 덱이 비어 있으면 null.	String lastElement = deque.peekLast();
offerFirst(E e)	덱의 앞부분에 요소를 추가한다. 공간이 부족하면 false, 성공 시 true.	boolean success = deque.offerFirst("Orange");
offerLast(E e)	덱의 뒷부분에 요소를 추가한다. 공간이 부족하면 false, 성공 시 true.	boolean success = deque.offerLast("Grape");
pollFirst()	덱의 앞부분에서 요소를 제거하고 반환한다. 덱이 비어 있으면 null.	String firstPoll = deque.pollFirst();
pollLast()	덱의 뒷부분에서 요소를 제거하고 반환한다. 덱이 비어 있으면 null.	String lastPoll = deque.pollLast();

---

문제

정수 배열 arr가 주어진다. 이 배열을 이용하여 새로운 배열 stk를 만들어야 한다.

작업 흐름

1. 변수 초기화:

   • 변수 i를 만들어 초기값을 0으로 설정한다.

2. 반복 작업:

   • i가 arr의 길이보다 작으면, 아래 작업을 반복한다:

   1. stk가 빈 배열일 경우:

      • arr[i]를 stk에 추가하고, i에 1을 더한다.

   2. stk에 원소가 있고, stk의 마지막 원소가 arr[i]보다 작을 경우:

      • arr[i]를 stk의 뒤에 추가하고, i에 1을 더한다.

   3. stk에 원소가 있고, stk의 마지막 원소가 arr[i]보다 크거나 같을 경우:

      • stk의 마지막 원소를 stk에서 제거한다.

3. 반복 후:

   • 위의 작업을 마친 후, 만들어진 stk를 반환한다.

문제 링크

풀이

import java.util.*;

class Solution {
    public int[] solution(int[] arr) {
        
        Deque<Integer> deque = new ArrayDeque<>();
        
        for(int i = 0; i < arr.length;) {
            // stk가 비어있으면 arr[i]를 추가
            if (deque.isEmpty()) {
                deque.addLast(arr[i]);  // 뒤에 추가
                i++;
            }
            // stk의 마지막 원소가 arr[i]보다 작으면 arr[i]를 추가
            else if (deque.peekLast() < arr[i]) {
                deque.addLast(arr[i]);  // 뒤에 추가
                i++;
            }
            // stk의 마지막 원소가 arr[i]보다 크거나 같으면 마지막 원소를 제거
            else {
                deque.removeLast();  // 뒤에서 제거
            }
        }
        
        // Deque를 배열로 변환
        int[] stk = new int[deque.size()];
        int index = 0;
        for (int value : deque) {
            stk[index++] = value;
        }
        
        return stk;
    }
}