27. Remove Element

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

주어진 조건

• 정수 배열 nums, 정수 val
• num1과 num2의 요소 개수를 나타내는 정수: m, n

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        nums = [i for i in nums if i != val]
        return len(nums)

문제

nums에서 val이 포함된 모든 항목을 제거한다.

nums에 남아있는 요소 개수를 return 해야한다.

---

나의 풀이

처음에는 val의 값을 제거한 list를 nums에 새로 할당하도록 하기 위해 list comprehension을 사용해 아래와 같이 구현하였다. 하지만 nums 자체에서 변경이 일어나야 테스트가 통과하는 것을 깨달았다.

시도 1

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        nums = [i for i in nums if i != val]
        return len(nums)

따라서 간단하게 val의 값이 존재하지 않을 때까지 remove 함수를 실행해 val 값과 일치하는 요소를 제거하도록 구현하였다.

구현 코드

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

---

다른 풀이

class Solution(object):
    def removeElement(self, nums, val):
        count = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[count] = nums[i]
                count += 1
        return count

위의 풀이는 nums의 길이만큼 반복하며, val 값이 아닌 요소들로만 처음부터 차곡차곡 넣는 방식이다.

시간 복잡도

내 코드는 사실 시간복잡도가 O(n) 같아 보이지만, 사실상 python의 list.remove() 함수의 시간 복잡도가 O(n)이기 때문에 시간 복잡도가 O(n^2) 이다.

하지만 위의 풀이는 O(n)이다. 코테 문제를 풀 때는, 내장 함수의 시간복잡도까지 고려해야 한다는 것을 다시 한 번 상기시켜주는 문제였다. (코드가 짧다고 좋은 게 아님 !)