27. Remove Element

👩‍💻 문제

 

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:

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.
Return k.

 

 

💡 훨씬 더 효율적인 풀이 1번

    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        for num in nums:
            if num != val:
                nums[index] = num
                index += 1
        nums[:] = nums[:index]
        return index

 

✍️ 해설

* Time Complexity = O(n)

for loop가 한 개 있으니까 ! 리스트를 한 번만 순회하면서, val과 같지 않은 애들만 앞으로 빼고 있다. 

다만, 이렇게 하면 nums의 뒤에 만약에 val과 같은 원소들이 았다면 그 친구들은 사라지지 않고 그대로 남아있게 된다 ㅇ_ㅇ

그러니까 nums[:] = nums[:k] 까지로 해서, 뒤에 있는 애들을 제거해주도록 한다!

 

val 과 다른 숫자들을 세는 걸 k로 둔다

nums에서, val과 같은 애들을 삭제해야 되잖나

[1,2,3,3,3,4,5], val = 3 이면

반환값은 1,2,4,5에 해당하는 4

그리고 nums 리스트는 다른 값들만 채워져 있어야 한다 [1,2,4,5]

 

val과 같은 값을 만나면, 채우면 안되니까

index는 그 자리에 계속 있는다. 3은 그대로 for loop를 통해서 자연스럽게 건너뛰게 되고,

나머지 Index 자리에 4, 5가 채워지게 된다 

띠용

 

 

💡 이런 방법도 있다!

    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums :
            nums.remove(val)   
        return len(nums)

아예 val을 remove 해버리는거다. 근데 비효율적이다. 기본적으로 리스트에서 뭘 제거하는 건 pop, remove 둘 다 O(n)임

따라서 전체 time complextiy = O(n^2) 이 돼버린다 =_=

 

💡 더 안좋은 코드 2번

    def removeElement(self, nums: List[int], val: int) -> int:
        index = 0
        while index < len(nums):
            if nums[index] == val:
                nums.pop(index)
                continue
            index += 1
        return len(nums)

 

* Time Complexity = O(n^2)

while 루프에서 한 번 n

pop을 하면서 계속 요소들을 앞으로 이동시키니까, 거기서 또 n

n*n = n^2

 

 

🥳 배운점

흐엥 뇌가 필요해요

굳이 리스트에서 제거할 필요 없고, nums의 0부터 쭉쭉 인덱스 올라가면서, 그 해당 자리만 바꿔주면 된다

[1,2,3,4,4,4] 에서 val = 4 라면

[1,2,3] 까지만 찰텢..