[리트코드] 27. Remove Element

문제

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

Contraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100 

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).

 

---

✔ 문제접근 #1 순차탐색[통과] ⭕

Intuition

배열의 각 요소를 val값과 비교하여 서로 같지 않다면 배열의 맨 앞부터 차례대로 넣어준다.

Algorithm

idx는 데이터를 삽입할 위치를 나타낸다. 배열의 각 요소를 순차적으로 탐색하여 val과 값이 같지 않다면 idx의 위치에 넣어주고 idx를 +1 해준다.

마지막 요소까지 데이터를 넣고 나면 idx값이 조건을 만족하는 데이터의 개수가 되므로 idx를 반환한다.

    def removeElement(self, nums: List[int], val: int) -> int:

        idx = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[idx] = nums[i]
                idx += 1
        
        return idx

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • num1 배열을 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(1)
  
  • 기존의 num1 배열을 재사용하기 때문에 추가적인 메모리를 사용하지 않는다.

---

기타풀이 및 회고

removeElement 의 반환값인 k를가지고 nums의 요소를 검사하는 것 같다. k의 길이만큼 검사하여 조건을 만족하면 통과이기 때문에 in-place방식으로 해결이 가능하다. 만약 이러한 조건이 없었다면 최종 idx의 위치를 포함하여 맨뒤의 요소까지 전부 null값처리를 해주면 될 것 같다.

nums = [3, 2, 2, 3] -> 결과 : k = 2, [2, 2, 2, 3] == [2, 2, null, null]