[Two Pointers] 80. Remove Duplicates from Sorted Array II

80. Remove Duplicates from Sorted Array II

 

https://youtu.be/ycAq8iqh0TI?si=xnT3SvO1n9jkMNVq

 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0  # 중복되지 않은 요소를 저장할 위치를 추적하는 포인터
        prev = nums[0] - 1  # 이전에 저장된 값을 추적하기 위한 변수, nums[0]보다 작은 값으로 초기화
        cnt = 0  # 현재 숫자가 몇 번 등장했는지 추적

        # 배열을 순회하며 중복을 제거
        for i in range(len(nums)):
            if nums[i] > prev:  # 새로운 값이 나왔을 때
                nums[k] = nums[i]  # 새로운 값을 nums[k] 위치에 저장
                k += 1  # 다음 저장 위치로 이동
                cnt = 1  # 새로운 값의 등장 횟수를 1로 초기화
                prev = nums[i]  # 현재 값을 이전 값으로 업데이트
            elif nums[i] == prev and cnt < 2:  # 동일한 값이지만 최대 2번까지 허용
                nums[k] = nums[i]  # 값을 nums[k] 위치에 저장
                k += 1  # 다음 저장 위치로 이동
                cnt += 1  # 동일한 값의 등장 횟수 증가
            else:  # 동일한 값이 2번 이상 등장한 경우
                cnt += 1  # 등장 횟수만 증가하고 저장은 하지 않음

        return k  # 중복되지 않은 요소의 개수 반환

 

최종 코드

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 주어진 nums 배열은 비내림차순 정렬되어 있음 (즉, 같거나 증가하는 순서)
        # 중복 허용은 최대 2번까지, 그 이상은 제거해야 함

        l, r = 0, 1              # l은 중복을 허용할 위치, r은 현재 검사 중인 위치
        curCount = 0            # 현재 숫자가 몇 번 중복되었는지 저장

        for r in range(1, len(nums)):
            if nums[l] != nums[r]:
                # 새 숫자가 나오면 중복 카운터 초기화
                curCount = 0
                l += 1
                nums[l] = nums[r]  # 새 숫자를 l 위치에 저장
            else:
                # 현재 숫자가 이전과 같은 경우 (중복)
                curCount += 1
                if curCount == 1:
                    # 같은 숫자가 처음 중복되는 경우는 허용 (즉, 총 2번까지 허용됨)
                    l += 1
                    nums[l] = nums[r]  # 허용된 중복을 l 위치에 저장
                # curCount > 1인 경우는 아무 처리 없이 건너뜀 (즉, 삭제 효과)

		# 배열 index 0부터 시작하므로, 
        # 수정한 배열개수: l+1 반환
        return l + 1  # 중복 제거 후의 배열 길이 반환