Skip to main content

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

Remove Duplicates from Sorted Array 2​

오름차순으로 정렬된 정수 배열 nums가 주어지면 각 고유 요소가 최대 두 번 나타나도록 일부 중복을 제자리에서 제거합니다. 요소의 상대적 순서는 동일하게 유지되어야 합니다.

일부 언어에서는 배열 길이를 변경할 수 없으므로 대신 결과를 배열 nums의 첫 번째 부분에 배치해야 합니다. 보다 공식적으로, 중복 항목을 제거한 후 k개 요소가 있는 경우 nums의 처음 k개 요소가 최종 결과를 보유해야 합니다. 처음 k개 요소 외에 무엇을 남겨두는지는 중요하지 않습니다.

숫자의 첫 번째 k 슬롯에 최종 결과를 넣은 후 k를 반환합니다. 다음 어레이에 추가 공간을 할당하지 마세요. O(1) 추가 메모리를 사용하여 입력 배열을 내부에서 수정하여 이를 수정해야 합니다.

입출력 예제​

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 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,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 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
    """
    i = 1 # 현재 인덱스를 1로 초기화
    k = 0 # 중복 횟수를 나타내는 변수를 0으로 초기화

    while i < len(nums): # 현재 인덱스가 nums 배열의 길이보다 작을 경우 반복, 즉 nums의 모든 인덱스를 순회
      if nums[i] != nums[i-1]: # 만약 현재 값과 이전 값이 다를 경우 중복이 없으므로 연속된 중복의 개수를 나타내는 k를 0으로 다시 초기화
        k = 0
      else: # 현재 값과 이전 값이 같을 경우 k를 1 증가하여 현재 중복이 1회 발생하였음을 나타냄
        k += 1

      if k >= 2: # 중복이 2회 이상 발생할 경우 현재 요소값을 제거
        nums.remove(nums[i]) # 제거할 경우 다음 순회 시 현재 인덱스 위치에 다음 요소 값이 위치하게 되므로 인덱스를 나타내는 i값을 증가시키지 않는다.
      else: # 중복이 2회 이상 발생하지 않은 경우 다음 요소를 순회하기 위해서 i를 증가
        i += 1

이전 인덱스와 비교해야하므로 처음에 인덱스를 나타내는 i의 값을 1로 초기화한 뒤 nums 배열의 총 길이만큼 순회하게 되며 만약 현재 인덱스의 요소값과 이전 인덱스의 요소값이 다를 경우 k를 0으로 다시 초기화하고 값이 같을 경우 k에 1을 더하여 중복 횟수를 늘려준다. 문제에서 최대 2번 중복이 허용된다고 하였으므로 k의 값이 1일 경우 연속된 두 요소가 중복됨을 나타내고 k의 값이 2일 경우 연속된 세 요소가 중복됨을 나타내므로 k가 2보다 클 때 현재 요소의 값을 제거한다. 제거할 때에는 다음 순회때 현재 인덱스 요소 값에 다음 요소가 위치하게 되므로 i를 증가시키지 않고 제거되지 않을 경우에 다음 요소를 이어서 순회하기 위해서 인덱스를 추가합니다.

이 코드는 Runtime 39ms (46.40%)이며 Memory는 13.27MB (74.62%)로 런타임 시간이 다른 유저에 비하여 다소 긴 편입니다.

런타임이 가장 최적화된 코드 (0.02% / 14ms)​

class Solution(object):
  def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    i = 0 # 인덱스를 나타내는 변수
    for num in nums: # nums 배열 순회
      if i < 2 or num != nums[i-2]:
        nums[i] = num
        i += 1
    return i

위 코드는 런타임 속도가 가장 짧은 코드로 nums를 순회하면서 현재 nums의 요소와 이 요소의 두 번째 전 요소가 같지 않을 경우 1번 이상의 중복이 일어난 것이 아니므로 이 경우에만 nums 배열에 순회한 요소들을 저장합니다. 조건문에 i가 2보다 작은 경우도 추가되었는데 이 경우는 두 번째 요소 순회 전까지는 두 번째 전 요소가 존재하지 않으므로 반복문을 정상적으로 순회시키기 위함입니다.