[Programmers] #181844 - 배열의 원소 삭제하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

정수 배열 arr에 대해 delete_list에 존재하는 원소는 제거한 후 남은 원소들을 순서를 유지해서 반환하는 문제로 delete_list를 통해 방문 체크 배열을 만들거나, 해시 집합을 활용하거나, 원소를 직접 제거하는 방식으로 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N + M)$	$O(N + M)$

($N$ = arr의 길이, $M$ = delete_list의 길이. Java는 방문 배열이 값 범위(1,000)로 고정된 상수 크기라 실질 공간이 출력 크기인 $O(N)$이다. C++은 delete_list 원소마다 std::erase로 arr 전체를 훑어 시간이 $O(N \times M)$이고, 인자를 제자리 수정해 그대로 반환하므로 공간은 $O(1)$이다)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int[] delete_list) {
        boolean[] seen = new boolean[1 + 1000];
        for (int x : delete_list) {
            seen[x] = true;
        }

        List<Integer> list = new ArrayList<>();
        for (int x : arr) {
            if (!seen[x]) list.add(x);
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> arr, vector<int> delete_list) {
    for (int x : delete_list) erase(arr, x);
    return arr;
}

std::erase로 바로 제거하는 방식으로 해결했다.

def solution(arr, delete_list):
    seen = set(delete_list)
    return [x for x in arr if x not in seen]

---