[알고리즘] 배열 중복 제거 시 정렬을 먼저 하는 이유

배열에서 중복된 값을 제거하기 위해서는 일반적으로 우선 배열을 정렬한다. 오름차순 정렬을 하면 중복된 값들이 인접한 위치에 모여 중복을 쉽게 찾을 수 있기 때문이다. 예를 들어, 정렬되지 않은 배열에서 중복을 찾으려면 배열의 모든 요소를 하나씩 비교해야 한다. 하지만 정렬된 배열에서는 중복된 값들이 연속해서 나타나기 때문에 중복을 찾는 과정이 간단해진다.

 

결국은 시간 복잡도를 줄이기 위함이다. 정렬된 배열에서 중복을 찾는 것은 인접한 값들만을 비교하면 되기 때문에 추가적인 반복문이나 자료구조를 사용할 필요가 없어진다. 반면, 정렬되지 않은 배열에서 중복을 찾으려면 모든 요소를 비교해야 하므로 시간 복잡도가 크게 증가할 수 있다.

 

반응형

 

예를 들어, 주어진 배열이 [4, 2, 1, 2, 4, 3, 1]이라고 가정해 보자. 이 배열을 오름차순으로 정렬하면 [1, 1, 2, 2, 3, 4, 4]가 된다. 이제 중복을 제거하기 위해 인접한 값들을 비교하면서 중복된 값을 제거한다. [1, 1, 2, 2, 3, 4, 4]에서 중복된 값은 [1, 2, 4]입니다. 따라서 중복을 제거한 배열은 [1, 2, 3, 4]가 된다.

 

정렬과 중복 제거를 한 번에 처리하는 파이썬 예제 코드는 아래와 같다.

def remove_duplicates(arr):
    arr.sort()  # 주어진 배열을 오름차순으로 정렬한다.

    n = len(arr)
    if n == 0 or n == 1:
        return arr  # 배열에 중복된 값이 없거나 하나밖에 없다면 그대로 반환한다.

    # 중복을 제거하는 과정
    j = 0
    for i in range(n - 1):
        if arr[i] != arr[i + 1]:
            arr[j] = arr[i]
            j += 1

    arr[j] = arr[n - 1]
    return arr[:j + 1]  # 중복이 제거된 배열을 반환한다.

파이썬에서는 정렬을 수행하기 위해 sort() 함수를 사용한다. 그러나 입력으로 주어진 배열이 이미 정렬되어 있는 경우, 당연히 정렬 과정이 생략된다.

 

참고로 sort() 함수도 정렬을 수행하는 과정에서 시간 복잡도를 가진다. sort() 함수를 사용하여 배열을 정렬하는 과정에서 소요되는 시간 복잡도는 O(n log n)이다. 일반적인 정렬 알고리즘인 퀵소트(Quicksort)나 머지소트(Mergesort)는 평균적으로 O(n log n)의 시간 복잡도를 가지며, 힙소트(Heapsort)는 항상 O(n log n)의 시간 복잡도를 가진다.

위 코드에서 중복을 제거하는 과정은 O(n)의 시간 복잡도를 가지고, sort() 함수는 O(n log n)의 시간 복잡도를 가진다. 전체 코드의 빅오 시간 복잡도를 구할 때에는 더 큰 시간 복잡도를 기준으로 한다. 따라서 전체적인 시간 복잡도는 O(n log n)이다.