[LeetCode] Remove Element

 

목차

 

 

문제

• 특정 리스트에서 특정 값들을 모두 제거하고 남은 리스트의 길이를 구하는 문제입니다.
• 예시

  • Input: nums = [3,2,2,3], val = 3
    Output: 2, nums = [2,2,_,_]

  • Input: nums = [0,1,2,2,3,0,4,2], val = 2
    Output: 5, nums = [0,1,4,0,3,_,_,_]

• 제약조건
  • • 0 <= nums.length <= 100
    • 0 <= nums[i] <= 50
    • 0 <= val <= 100

문제 풀이

풀이 1 : Two Pointers

• 풀이
  • 그냥 nums.remove(val)를 통해서 해당 원소가 없을 때까지 리스트에서 제거해 주는 작업은 최대 O(n!)의 시간복잡도가 소모될 것입니다.
  • 하지만 이를 투 포인터를 이용해서 nums안의 모든 val을 제거하고, 모든 원소를 앞으로 당기는 작업을 O(n)만에 가능해집니다.
  • 
• 코드

  • class Solution:
        def removeElement(self, nums: List[int], val: int) -> int:
            i = 0
            n = len(nums)
            for j in range(n):
                if nums[j]!=val:
                    nums[i]=nums[j]
                    i+=1
            return i

• 시간복잡도
  • O(n)

알게 된 내용

• 특정 값을 리스트에서 모두 제거할 때는 값이 여러 개일지도 모르기 때문에 del이나 remove를 사용하기보다는 위처럼 투포인터를 사용하여 제거한 뒤 기존 배열에 nums[:i]로 불러오는 것이 효율적입니다. 

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/526/deleting-items-from-an-array/3247/