[알고리즘/Python] LeetCode 27.Remove Element

문제

https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150

 

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

 1. Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
 2. Return k.
 
Example 1:
Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).
 
Constraints:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

---

💡 접근방법: 정렬 라이브러리 사용

1. val와 값이 같은 원소를 대체하기 위한 EMPTY 변수를 모든 원소의 값보다 항상 큰 값인 51로, val과 값이 같지 않은 원소의 개수를 나타내는 변수 k를 0으로 초기화한다.

2. nums 배열을 순회하면서 원소의 값이 val과 같은 경우 값을 EMPTY로 대체해준다. 원소의 값이 val과 다르다면 k를 1 증가시킨다.

3. 순회가 끝나면 nums를 오름차순 정렬한다. 그 결과로 nums배열의 인덱스 0 부터 len(nums) - k -1까지는 값이 val과 다른 원소들이 오름차순 정렬되고, 그 이후의 k개의 원소들은 EMPTY 값을 가진다.

4. k를 반환한다.

 

class Solution(object):
    def removeElement(self, nums, val):
        EMPTY = 101
        k = 0
        for index, num in enumerate(nums):
            if num == val:
                nums[index] = EMPTY
            else:
                k += 1
        nums.sort()
        return k

✔️시간 복잡도 및 공간 복잡도

시간 복잡도: O(NLogN). 배열을 순회하는데 O(N), 배열을 정렬하는데 O(NLogN) 시간이 소요되므로 총 O(NlogN)복잡도를 가진다.

 

공간 복잡도: O(1). 주어진 배열 내에서 값을 정렬하므로 추가 공간이 필요하지 않다.

---

⚒️개선: 값 덮어쓰기

값이 val과 같지 않은 원소들을 배열의 앞에서부터 채워가면 정렬을 하지 않아도 되어 시간 복잡도를 O(NLogN)에서 O(N)로 줄일 수 있다. 

 

1. 변수 index는 다음으로 val과 값이 같지 않은 원소들을 저장할 인덱스를 가리키는를 가리키며 0으로 초기화한다.

2. nums 배열을 순회하면서 원소의 값이 val과 같지 않은 경우 그 값을 nums[index]에 덮어쓰고 index를 1 증가시킨다. 

3.  index를 반환한다.

 

    def remove_element(self, nums, val):
        index = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[index] = nums[i]
                index += 1
        return index

 

index는 다음으로 삭제 대상이 아닌 원소를 저장할 인덱스를 나타내면서 동시에 삭제 대상이 아닌 원소들의 개수를 나타낸다.  index는 항상 val과 비교할 원소의 인덱스를 나타내는 i보다 작거나 같다. 

 

Example 1의 경우 nums는 [3,2,2,3]이고 val은 3이다. 순회를 하고 나면 nums는 [2,2,2,3]이 되고 index는 2를 가리킨다. val과 값이 같은 원소들을 앞에서부터 채워나가게 되고, index 2의 값 2는 nums[index1]에 복사된다. 중복 저장된 것이지만 배열의 앞에서부터 k개(반환하는 값, index)의 원소를 유효한 원소로 보기 때문에 통과가 가능하다.

---

🔖 정리

◎ 이 문제의 경우 배열의 길이가 100밖에 되지 않기 때문에  O(NLogN)복잡도를 가지는 정렬 알고리즘을 사용할 수 있지만, 배열의 길이가 100만을 넘어간다면 연산횟수가 지나치게 많아질 수 있다. 따라서 정렬 알고리즘보다 더 빠르게 실행할 수 있는 알고리즘을 찾는 것이 좋다.