C#으로 정렬된 배열에서 중복을 제거하고 고유한 값만 담은 새 배열 반환하는 방법

개요

배열이 이미 정렬되어 있다면 두 개의 포인터(투 포인터) 기법을 활용해 효율적으로 중복을 제거할 수 있습니다. 느린 포인터 i와 빠른 포인터 j를 두고, nums[i] == nums[j]인 동안에는 j를 계속 증가시켜 중복된 값을 건너뜁니다.

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

순회가 끝나면 필터링된 배열의 앞부분에서 유효한 인덱스(index)까지의 요소들을 새로운 배열에 복사한 뒤, 그 새 배열을 반환하면 됩니다.

시간 복잡도

O(N) — 배열을 한 번만 순회하므로 선형 시간 복잡도를 가집니다.

예제 코드

using System;
namespace ConsoleApplication{
    public class Arrays{
        public int[] RemoveDuplicatesFromSortedArrayAndReturnArray(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;
                }
            }
            int[] newarr = new int[index];
            for (int i = 0; i < index; i++){
                newarr[i] = arr[i];
            }
            return newarr;
        }
    }
    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.RemoveDuplicatesFromSortedArrayAndReturnArray(arr);
            for (int i = 0; i < res.Length; i++){
                Console.WriteLine(res[i]);
            }
            Console.ReadLine();
        }
    }
}

실행 결과

0 1 2 3 4

코드 설명

위 예제에서 입력 배열 { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 }는 이미 오름차순으로 정렬되어 있습니다. 루프 안에서 인접한 두 요소를 비교하여 값이 다를 때만 앞쪽 위치에 값을 덮어쓰고 index를 증가시킵니다. 최종적으로 index는 중복이 제거된 요소의 개수가 되며, 이 크기만큼 새 배열을 생성해 결과를 반환합니다.