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

Oct 11, 2025

💡

문제 설명

아무 원소도 들어있지 않은 빈 배열 X가 있습니다. 길이가 같은 정수 배열 arr과 boolean 배열 flag가 매개변수로 주어질 때, flag를 차례대로 순회하며 flag[i]가 true라면 X의 뒤에 arr[i]를 arr[i] × 2 번 추가하고, flag[i]가 false라면 X에서 마지막 arr[i]개의 원소를 제거한 뒤 X를 return 하는 solution 함수를 작성해 주세요.

💡

제한사항

1 ≤ arr의 길이 = flag의 길이 ≤ 100

arr의 모든 원소는 1 이상 9 이하의 정수입니다.

현재 X의 길이보다 더 많은 원소를 빼는 입력은 주어지지 않습니다.

입출력 예

arr	flag	result
[3, 2, 4, 1, 3]	[true, false, true, false, false]	[3, 3, 3, 3, 4, 4, 4, 4]

입출력 예 설명

입출력 예 #1

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

i	flag[i]	arr[i]	X
ㅤ	ㅤ	ㅤ	[]
0	true	3	[3, 3, 3, 3, 3, 3]
1	false	2	[3, 3, 3, 3]
2	true	4	[3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4]
3	false	1	[3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4]
4	false	3	[3, 3, 3, 3, 4, 4, 4, 4]

따라서 [3, 3, 3, 3, 4, 4, 4, 4]를 return 합니다.

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


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;
    }
}

성능 차이가 있음

스택 방식이 더 좋음