C#으로 정렬된 배열의 중복 요소를 제거하고 새로운 길이 반환하기

배열이 이미 정렬되어 있다면, 투 포인터(Two Pointers) 기법을 활용하여 중복을 효율적으로 제거할 수 있습니다.

알고리즘 동작 원리

두 개의 포인터 i와 j를 사용합니다. 여기서 i는 느린 포인터(slow-runner), j는 빠른 포인터(fast-runner) 역할을 합니다.

nums[i]와 nums[j]가 같은 동안에는 j를 계속 증가시켜 중복 값을 건너뜁니다.

nums[j] != nums[i]인 지점을 만나면 중복 구간이 끝난 것이므로, 해당 값을 nums[i + 1]에 복사합니다. 그런 다음 i를 증가시키고, j가 배열의 끝에 도달할 때까지 같은 과정을 반복합니다.

시간 복잡도

O(N) — 배열을 한 번만 순회하므로 매우 효율적입니다.

C# 구현 예제

using System;
namespace ConsoleApplication{
    public class Arrays{
        public int RemoveDuplicatesFromSortedArrayAndReturnLength(int[] arr){
            int index = 1;
            for (int i = 0; i < arr.Length - 1; i++){
                if (arr[i] != arr[i + 1]){
                    arr[index] = arr[i + 1];
                    index++;
                }
                else{
                    continue;
                }
            }
            return index;
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
            int res = a.RemoveDuplicatesFromSortedArrayAndReturnLength(arr);
            Console.WriteLine(res);
            Console.ReadLine();
        }
    }
}

실행 결과

5

위 예제에서 입력 배열 { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 }는 중복이 제거된 후 { 0, 1, 2, 3, 4 }가 되며, 고유한 요소의 개수인 5가 반환됩니다.