[LeetCode/Java] 26. Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

 

[문제]

정렬된 정수 배열 nums에서 중복을 제거하여 배열의 고유한 원소들로만 이루어진 부분을 반환해야 한다.

중복을 제거한 후에도 배열의 순서는 유지되어야 하며, 중복을 제거한 후의 길이를 반환해야 한다. 배열의 첫 k개의 요소가 중복이 제거된 부분을 나타낸다.

 

[문제 조건]

1. 정렬된 배열이 주어지기 때문에, 중복된 숫자들이 연속해서 등장한다.
2. 추가 공간을 사용하지 않고, 제자리에서(in-place) 중복을 제거해야 한다.
   • 새로운 배열이나 추가 자료구조(Set 등)를 사용하면 안 된다.
3. 반환값으로 중복이 제거된 배열의 길이(k)를 반환한다.
4. 첫 k개의 요소가 중복을 제거한 상태여야 한다.
   • Set을 사용하면 순서가 보장되지 않아 문제 요구사항을 만족하지 못한다.

 

[접근 방법]

1. 투 포인터 사용
   • i는 중복이 없는 부분의 마지막 인덱스를 가리킨다.
   • j는 중복이 있는 부분을 탐색한다.
2. 중복이 없는 경우
   • nums[i]와 nums[j]가 다르면, nums[i + 1]에 nums[j]를 복사하고, i를 증가시킨다.
3. 최종 길이
   • 배열의 처음 i + 1개 요소가 중복 제거된 배열이 된다.

 

[코드]

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

 

[코드 설명]

• i는 고유 원소의 마지막 인덱스를 가리키고, j는 중복 요소를 탐색하는 포인터로 사용한다.
• 중복이 없을 때 nums[i + 1]에 nums[j]를 복사하고 i를 증가시킨다.
• 최종 길이는 i + 1로 반환한다.
• 시간 복잡도 O(1)