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

문제 링크

---

1. 아이디어

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

---

2. 복잡도

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

($N$ = arr의 길이, $M$ = delete_list의 길이, $K$ = 값의 범위. Java는 방문 배열이 값의 범위 크기라 시간 $O(N + M + K)$, 공간 $O(N + K)$. C++는 delete_list 원소마다 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;
        }

        return Arrays.stream(arr).filter(x -> !seen[x]).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]

---