정렬된 배열에서 중복 제거 II (LeetCode P80)

문제 설명

정수 배열 nums가 오름차순으로 정렬되어 있습니다. 배열에서 일부 중복을 제거하여 각 고유 요소가 최대 두 번까지 등장할 수 있도록 해야 합니다. 단, 요소의 상대적인 순서는 유지해야 합니다.

배열의 길이를 변경할 수 없는 경우가 있으므로, 결과는 배열 nums의 처음 k개의 요소에 저장되어야 합니다. 즉, 중복을 제거한 후 k개의 요소가 nums의 처음 k 위치에 있도록 해야 합니다. 이후의 요소는 상관없습니다.

최종 배열의 길이 k를 반환하세요.

예제

입력:

nums = [1, 1, 1, 2, 2, 3]

출력:

5, (nums = [1, 1, 2, 2, 3, _])

해결 방법

배열을 순회하면서 중복되지 않은 요소를 저장할 위치를 나타내는 포인터(insertPos)를 유지합니다. 또한, 현재 숫자가 이미 한 번 중복되었는지를 추적하기 위해 불리언 변수(hasDuplicate)를 사용합니다.

풀이 과정:

1. 두 번째 요소(cur = 1)부터 반복을 시작합니다.
2. 현재 숫자가 nums[insertPos]와 같고 이미 한 번 중복되었다면 건너뜁니다.
3. 그렇지 않다면 nums[++insertPos]에 nums[cur]을 저장합니다.
4. 최종적으로 insertPos + 1을 반환하여 새로운 배열의 길이를 반환합니다.

코드 구현

function removeDuplicates(nums: number[]): number {
  let insertPos = 0
  let hasDuplicate = false

  for (let cur = 1; cur < nums.length; cur++) {
    if (nums[cur] === nums[insertPos] && hasDuplicate) continue

    hasDuplicate = nums[cur] === nums[insertPos]
    nums[++insertPos] = nums[cur]
  }

  return insertPos + 1
}

시간 및 공간 복잡도 분석

• 시간 복잡도: O(n), 배열을 한 번 순회하기 때문에 선형 시간 복잡도를 가집니다.
• 공간 복잡도: O(1), 추가적인 저장 공간 없이 배열을 직접 수정하여 해결합니다.

고려된 엣지 케이스

• 중복이 없는 배열: [1,2,3,4,5]
• 모든 요소가 동일한 배열: [2,2,2,2,2]
• 모든 숫자가 정확히 두 번씩 등장하는 배열: [1,1,2,2,3,3]
• 길이가 1인 배열: [1]

요약

이 접근 방식은 최소한의 추가 로직으로 중복을 제거하면서도 순서를 유지하는 데 효과적입니다. 시간 및 공간 복잡도 면에서도 최적화된 솔루션입니다.