Skip to main content

Remove Element

Remove Element​

정수 배열 nums와 정수 val이 주어지면 nums에서 발생하는 모든 val을 제자리에서 제거합니다. 요소의 순서는 변경될 수 있습니다. 그런 다음 val과 같지 않은 요소 수를 nums로 반환합니다.

nums의 요소 중 val과 다른 요소의 수를 k라고 가정합니다.

  • nums 배열을 변경하여 nums의 처음 k개 요소가 val과 다른 요소를 포함하도록 합니다. nums의 나머지 요소는 중요하지 않으며 nums의 크기도 중요하지 않습니다.
  • 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).

나의 풀이​

class Solution(object):
  def removeElement(self, nums, val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
    """

    k = 0
    for n in nums[:]:
      if n == val:
        nums.remove(n)
      else:
        k += 1
    return k

배열의 요소를 반복문을 순회하면서 요소를 삭제하게 될 경우 index out of range 에러가 발생하기 때문에 배열을 복사한 뒤 복사한 배열을 순회하면서 만약 val과 동일한 요소가 존재할 경우 원본 배열에서 해당 요소를 삭제합니다. 이렇게 하면 index out of range 에러가 발생하지 않으며 val이 아닐 경우 0으로 초기화한 k 변수에 1 값을 증가해줌으로써 원본 배열에서 val이 아닌 요소의 개수를 반환해줍니다.

위 코드는 Runtime 19ms (51.53%), Memory 13.08MB (98.01%) 입니다.

배열 요소를 삭제하는 파이썬 함수들의 시간 복잡도 비교​

pop(index)​

  • 평균적으로 O(n)이며 리스트의 마지막에서 요소를 제거하는 경우 O(1), 일반적으로 해당 위치부터 리스트의 끝까지 모든 항목을 이동해야 하므로 O(n)

remove(value)​

  • 평균적으로 O(n)이며 값이 리스트의 시작 부분에 있을 경우 O(1), 리스트 내에서 해당 값의 위치를 찾기 위해 최악의 경우 전체 리스트를 검색해야 하기 때문에 O(n)

del list[index]​

  • 평균적으로 O(n)이며, del은 pop과 유사하게 작동하며 특정 인덱스의 요소를 제거하면 그 이후의 모든 요소를 이동

list comprehension​

  • example: [x for x in list if x != val]
  • 평균 O(n), 리스트 컴프리헨션은 리스트의 각 요소를 한 번씩 확인

filter()​

  • 평균 O(n)이며 리스트의 각 요소를 한 번씩 확인

최적의 시간복잡도 측면에서 요소 제거 함수를 사용해야 한다면 pop 메서드를 사용할 때 제거하려는 요소를 마지막에 위치하도록 하거나 remove 메서드를 사용할 때는 제거하려는 요소를 리스트의 시작 부분에 위치하도록 합니다.

나의 다른 풀이​

class Solution(object):
  def removeElement(self, nums, val):
    """
    :type nums: List[int]
    :type val: int
    :rtype: int
    """
    k = 0 # nums배열의 val이 아닌 요소의 총 개수
    index_arr = [] # nums의 배열에서 val과 같은 요소의 인덱스 값이 담길 배열
    for i in range(len(nums)):
      if nums[i] == val: # val과 같을 경우 index_arr 배열에 추가
        index_arr.append(i)
      else:
        k += 1 # val이 아닐 경우 k 변수에 값을 1 증가

    lst_index = len(nums) - 1 # nums 배열의 마지막 인덱스 값으로 초기화
    for i in range(len(index_arr)-1, -1, -1): # index_arr 배열을 뒤부터 순회
      if index_arr[i] == lst_index: # index_arr의 값과 lst_index가 일치할 경우 val과 같은 nums 배열 요소의 값이 마지막에 위치하였다는 의미이므로 lst_index를 1 감소
        lst_index -= 1
      else:
        # 그렇지 않을 경우 마지막 요소와 스위치
        nums[index_arr[i]], nums[lst_index] = nums[lst_index], nums[index_arr[i]]
        # 스위치 한 후 lst_index를 1 감소
        lst_index -= 1
    return k

첫 반복문에서는 배열을 순회하면서 val과 같은 요소가 있을 경우 해당 요소의 인덱스를 index_arr 배열에 추가하고 val과 같은 요소가 아닐 경우 k 변수에 1을 추가합니다 여기서 k는 nums 배열에서 val과 같지 않은 수의 총 개수를 의미합니다. 다음 반복문을 순회하기 전에 lst_index에 nums의 마지막 요소 인덱스 값으로 초기화한 뒤 순회를 진행하며 이 반복문에서는 뒤부터 순회하게 됩니다. 뒤부터 순회할 때 만약 현재 인덱스 값이 마지막 인덱스와 같다면 lst_index를 -1해주며 현재 인덱스 값이 마지막 인덱스와 같지 않다면 nums의 해당 인덱스 요소와 lst_index를 스위칭하고 lst_index에 -1을 합니다. 요약하자면, 두번째 반복문에서는 val과 같은 요소를 맨 뒤로 이동시키게 됩니다. 이렇게 문제를 풀이한 이유는 nums의 배열에서 k길이만큼 요소를 출력할 때 val이 포함되어 있지 않으면 정답으로 인정되기 때문입니다.

위 코드는 이전 코드보다 성능이 좋지 않으며 Runtime 21ms (36.44%)이며 Memory 13.26MB(55.08%)입니다.

런타임이 가장 짧은 코드 (0.04% / 0ms)​

class Solution(object):
  def removeElement(self, nums, val):
    i = 0 # 유효한 인덱스를 0으로 초기화

    for x in nums: # nums 배열을 순회
      if x != val: # nums 배열을 순회하면서 val이 아닐 경우
        nums[i] = x # val이 아닌 요소를 nums 배열에 저장
        i += 1 # 인덱스 증가
    return i

이 코드를 봤을 때 들었던 생각은 "지금까지 내가 짠 코드는 뭐지?"라는 생각이 가장 먼저 들었습니다. 문제를 제대로 이해하였다면 첫 번째 코드처럼 요소를 삭제할 필요도 없었으며 위와 같이 유효 길이만큼의 요소에 val이 아닌 요소만 포함시키면 되었습니다.