[LEETCODE 150] - 26 Remove Duplicates from Sorted Array

 

LEETCODE 26번 문제는 오름차순으로 정렬된 정수배열 nums가 주어졌을때, 중복된 값을 제자리(In-place)에서 제거하여

서로 다른 값만 남기고, 그 서로 다른값의 개수 k를 반환하는 문제다.

추가 배열을 만들지 말아야 하며, 반환된 k 기준으로 배열의 앞쪽 k개의 요소가 중복 제거된 결과 여야 한다.

왼쪽으로 비교하면서 새로운값인지 직전에 저장한 값과 비교하는 형식이다.

Key Findings

입력 특징(중요): 배열이 이미 정렬되어 있음 → 중복 값이 연속으로 붙어 있음

핵심 기법: 투 포인터(Two Pointers)

 

• r: 읽기 포인터(현재 값을 확인)
• i: 쓰기 포인터(다음 “새로운 값”을 쓸 위치)

반환 값: 중복 제거 후 남는 고유 원소의 개수 i

---

Details

문제 요구사항 요약

 

• nums는 정렬된 배열
• 중복을 제거하되, 고유 원소들의 상대적 순서 유지가 필요함
• 결과적으로 :
  • nums[0..l-1] = 중복 제거된 값들
  • return l

---

알고리즘 작동 원리 (투 포인터)

 

정렬되어 있으니, 새로운 값인지 직전에 저장한 값과 비교하면 된다.

 

1. 예외처리 : 배열이 비어있으면 0 반환

2. 포인터 초기화 : l = 1(첫 원소는 무조건 고유값이므로 이미 포함)

3. 배열 순회 : r를 1부터 끝까지 돌면서 nums[r] != nums[r - 1] 이면 새로운 고유값 등장 

• nums[l] = nums[r] 로 앞쪽에 채워 넣고
• l += 1

4. 결과 반환

• l 반환

---

 

정답 코드(Python)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = 1
        for r in range(1, len(nums)):
            if nums[r] != nums[r - 1]:
                nums[l] = nums[r]
                l += 1
            r += 1
        return l

---

시간 복잡도

 

• 추가 메모리 없이 처리 → 공간 O(1)
• 한 번 순회 → 시간 O(n)