정렬 배열에서 중복 요소 제거

Remove Duplicates from Sorted Array

오름차순으로 정렬된 정수 배열 nums가 주어지면 각 고유 요소가 한 번만 나타나도록 중복 항목을 제자리에서 제거합니다. 요소의 상대적 순서는 동일하게 유지해야 합니다. 그런 다음 고유 요소 수를 nums로 반환합니다.

숫자는 고요 요소 수를 k로 간주하고 다음 작업을 수행해야 합니다.

• nums의 처음 k개 요소가 처음에 nums에 있었던 순서대로 고유한 요소를 포함하도록 배열 nums를 변경합니다. nums의 나머지 요소는 nums의 크기만큼 중요하지 않습니다.
• k를 반환합니다.

입출력 예제

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

나의 풀이

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

    memory = nums[0]
    k = 1
    for i in range(1, len(nums)):
      if memory != nums[i]:
        nums[k] = nums[i]
        k += 1
        memory = nums[i]

    return k

위 풀이는 2번 문제에서의 최적의 코드와 비슷한 유형으로 풀이를 했습니다. 메모리라는 변수에 오름차순으로 정렬된 nums 배열의 0번째 요소를 저장한 뒤에 1번 요소부터 마지막 요소까지 순회를 시작합니다. 동일하게 k 변수도 1로 초기화합니다. 만약 momory 값이 nums[i]와 같지 않다면 중복된 값이 아니므로 nums[k]에 해당 요소를 저장한 뒤 k 변수를 1 추가하여 다음 인덱스를 가르키게 합니다. 메모리 변수에도 마지막으로 저장된 요소를 저장합니다.

이 코드는 Runtime 56ms (86.18%)이고 Memory는 14.86MB(25.65%)로 사용 메모리가 높은 편입니다.

메모리를 적게 사용한 코드 (0.01% / 13.8MB)

class Solution(object):
  def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    i = 1
    while i < len(nums):
      if nums[i] == nums[i-1]: # 현재 인덱스가 이전 인덱스와 같을 경우
        nums.remove(nums[i]) # 현재 인덱스 요소를 제거
      else:
        i += 1 # 같지 않을 경우 1 증가

비교 대상을 변수를 초기화하여 값을 할당하고 비교하는 것이 아니라 현재 인덱스와 이전 인덱스를 비교함으로써 메모리를 보다 덜 사용하는 것을 알 수 있습니다.