[프로그래머스] 93. 빈 배열에 추가, 삭제하기

입출력 예

입출력 예 설명

• 예제 1번에서 X의 변화를 표로 나타내면 다음과 같습니다

코드 - 매번 새로운 배열 생성

import java.util.Arrays;

class Solution {
    public int[] solution(int[] arr, boolean[] flag) {
        int[] x = new int[0];
        
        for(int i = 0; i < flag.length; i++) {
            if(flag[i]) {
                // x에 arr[i] 값을 x2 번 추가
                int addCount = arr[i] * 2;
                for(int j = 0; j < addCount; j++) {
                    int[] newX = Arrays.copyOf(x, x.length + 1);
                    newX[newX.length - 1] = arr[i];
                    x = newX;
                }
                
            } else {
                // x에 arr[i]개의 원소를 제거
                int[] newX = Arrays.copyOf(x, x.length - arr[i]);
                x = newX;
            }
        }
        
        return x;
    }
}

• 시간 복잡도가 매우 높아질 수 있기 때문에 비효율임

코드 - 스택 방법

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

class Solution {
    /**
     * Arrays.copyOf 반복 대신 ArrayDeque를 사용하여 O(1) 성능으로 배열의 동적 추가/제거를 처리합니다.
     */
    public int[] solution(int[] arr, boolean[] flag) {
        // Deque를 사용하여 O(1)로 맨 뒤 요소 추가/제거를 수행합니다.
        // Deque는 Stack과 Queue 기능을 모두 제공하는 가장 효율적인 클래스입니다.
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < flag.length; i++) {
            int value = arr[i];
            
            if (flag[i]) {
                // flag가 true: arr[i] 값을 2배 수만큼 deque의 꼬리(끝)에 추가
                int addCount = value * 2;
                
                // O(1) 연산으로 반복 추가
                for (int j = 0; j < addCount; j++) {
                    deque.offerLast(value); 
                    // offerLast는 배열의 끝에 추가(append)하는 논리와 일치합니다.
                }
                
            } else {
                // flag가 false: deque의 꼬리에서 arr[i]개의 원소를 제거
                int removeCount = value;
                
                // ⚠️ 안전성 확보: 제거할 개수가 현재 크기보다 크지 않도록 제한
                int actualRemoveCount = Math.min(removeCount, deque.size());
                
                // O(1) 연산으로 반복 제거
                for (int j = 0; j < actualRemoveCount; j++) {
                    deque.pollLast(); 
                    // pollLast는 배열의 끝에서 제거(pop)하는 논리와 일치합니다.
                }
            }
        }
        
        // 2. 최종 결과를 int 배열로 변환
        int[] result = new int[deque.size()];
        int index = 0;
        
        // Deque를 순회하며 결과를 int 배열에 저장합니다.
        // ArrayDeque의 iterator는 삽입 순서를 유지합니다.
        for(int item : deque) {
            result[index++] = item;
        }
        
        return result;
    }
}

• 성능 차이가 있음

• 스택 방식이 더 좋음