26. Remove Duplicates from Sorted Array

문제 링크: https://leetcode.com/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&envId=top-interview-150

주어진 조건

• 정수 배열 nums
• 각 고유 요소가 한 번만 나타나도록 중복된 요소를 nums에서 제거하자

문제

• nums가 아닌 nums의 요소 수 k를 return

---

나의 풀이

전에 풀었던 Remove Element 문제에서 이용했던 풀이를 이용해 풀었다.

nums에 요소들을 index 0부터 요소를 넣되, 만약 이미 같은 요소가 있다면, 넣지 않는다.

구현 코드

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums)):
            if nums[i] not in nums[:count]:
                nums[count] = nums[i]
                count += 1
        return count

---

다른 풀이

def removeDuplicates(self, nums: List[int]) -> int:
		slow, fast = 0, 1
		while fast in range(len(nums)):
			if nums[slow] == nums[fast]:
				fast += 1
			else:
				nums[slow+1] = nums[fast]
				fast += 1
				slow += 1

		return slow + 1

Two-Pointer를 사용한 코드이다.

slow: 중복이 아닌 요소를 넣을 nums의 index

fast: 중복이 아닌 요소를 탐색하는 nums의 index

• nums[slow]의 값과 nums[fast]의 값이 같으면, 중복 요소라 여기고 fast의 포인터 값 1 증가
• nums[slow]의 값과 nums[fast]의 값이 다르다면, nums[slow+1]에 해당 요소를 넣고, 두 포인터 값 모두 1씩 증가

두 배열을 이용해 조작하는 형태의 문제는 two pointer를 사용하는 것이 실행시간이 짧은 코드를 짜는 데에 유리한 것 같다.

시간 복잡도

내 코드는 for문이 반복될 때마다 nums[:count]에 있는 요소인지 확인하는 코드로 인해, 약 O(n^2)의 시간 복잡도가 나타난다.

위의 풀이는 nums의 길이만큼 반복하기만 하므로 시간 복잡도는 O(n).