26. 정렬된 배열에서 중복 항목 제거

이 문제는 정렬된 정수 배열에서 중복 요소를 제거하고, 각 고유한 요소가 한 번만 나타나도록 배열을 수정하는 것입니다. 배열의 처음 k개의 요소는 고유한 값으로 채워져야 하며, 나머지 요소들은 무시해도 됩니다. 이 문제를 해결하기 위해 '투 포인터' 기법을 사용합니다. 이제 코드를 단계별로 설명하겠습니다.

1. 알고리즘의 핵심 아이디어

이 문제의 핵심은 배열을 한 번만 순회하면서 중복을 제거하는 것입니다. 이를 위해 두 개의 포인터를 사용합니다:

• slow 포인터: 고유한 요소가 저장될 위치를 가리킵니다.
• fast 포인터: 배열을 순회하며 중복 여부를 확인합니다.

2. 코드의 주요 로직 설명

function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0;
    let slow = 1;
    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[fast] !== nums[fast - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

3. 각 단계별 동작 과정

1. 초기 조건 확인: 배열이 비어 있는 경우, 중복을 제거할 필요가 없으므로 0을 반환합니다.

   if (nums.length === 0) return 0;
   

2. 포인터 초기화: slow 포인터는 1로 초기화합니다. 이는 첫 번째 요소는 항상 고유하므로 두 번째 위치부터 새로운 고유 요소를 저장하기 위함입니다.

   let slow = 1;
   

3. 배열 순회: fast 포인터를 사용하여 배열의 두 번째 요소부터 끝까지 순회합니다.

   for (let fast = 1; fast < nums.length; fast++) {
   

4. 중복 검사 및 저장: fast 포인터가 가리키는 현재 요소가 이전 요소와 다르면, 이는 고유한 요소입니다. 따라서 slow 포인터가 가리키는 위치에 이 요소를 저장하고, slow 포인터를 증가시킵니다.

   if (nums[fast] !== nums[fast - 1]) {
       nums[slow] = nums[fast];
       slow++;
   }
   

5. 결과 반환: slow 포인터의 값은 고유한 요소의 개수를 나타내므로 이를 반환합니다.

   return slow;
   

4. 핵심 변수들의 역할

• slow: 고유한 요소가 저장될 위치를 추적합니다. 고유한 요소가 발견될 때마다 증가합니다.
• fast: 배열을 순회하며 현재 요소와 이전 요소를 비교하여 중복 여부를 확인합니다.

5. 왜 이 방법이 효과적인지

이 방법은 배열을 한 번만 순회하면서 중복을 제거하므로 시간 복잡도가 O(n)입니다. 이는 매우 효율적이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 또한, 정렬된 배열의 특성을 이용하여 인접한 요소만 비교하면 되므로 알고리즘이 간단하고 직관적입니다. 이러한 이유로 이 방법은 문제를 효과적으로 해결합니다.