LeetCode 26. Remove Duplicates From Sorted Array (Python)

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Remove Duplicates from Sorted Array - LeetCode

Solution 

• 시간복잡도: O(n)
• 공간복잡도: O(1)

아이디어(Brute-Force)

중복이 없는 상태의 길이를 반환하라는 문제인데, 단순히 중복되지 않는 수의 갯수를 세서 이를 반환하는 식으로 구함. 

.. 이라고 생각했는데, 배열의 숫자도 그대로 (in-place) 업데이트를 해줘야 테스트케이스를 전부 통과할 수 있다.  

1. 맨 첫 요소(curr)을 저장하고 cnt를 1로 초기화한다. 

2. 배열의 요소를 맨 첫 요소를 제외하고 순회한다. 

3. 1~n-1까지 순회하고, curr과 값이 같으면 넘어가고, 다르다면 curr을 현재 값으로 업데이트하고 cnt를 1 증가시킨다. 

def removeDuplicates(nums: List[int]) -> int:
    if len(nums) <= 0:
        return 0

    curr = nums[0]
    cnt = 1

    for i in range(1, len(nums)):
        if curr != nums[i]:
            curr = nums[i]
            nums[cnt] = curr # 길이만 구하면 없어도 되지만, 배열 수정을 하라고 했으므로 필요함
            cnt+= 1

    return cnt