정수 배열에서 중복 값 (요소) 제거하기 (2) - O(nlogn)

이번 시간에는, 정수 배열에서 중복 값 (요소) 를 제거하는 방법에 대해 설명드리고자 합니다. 지난 번 강의에서 이미 첫 번째 방법을 설명드렸습니다.

(정수 배열에서 중복 값 (요소) 제거하기 (1) - O(n2) 참고)

http://kkikkodev.tistory.com/55

첫 번째 방법은, 시간 복잡도가 O(n2) 이기 때문에, 이번에는 이를 개선하여 시간 복잡도를 O(nlogn) 으로 구현한 방법을 소개드리겠습니다. 마찬가지로, 소스코드 설명에 앞서, 알고리즘을 도식화해서 설명드리겠습니다.

arr 는 정렬할 기존 정수 배열을 뜻합니다. 크기는 10 개로 지정하였고, 제가 1, 3, 4, 1, 7, 2, 5, 4, 3, 9 의 임의의 정수들을 저장하였습니다. elements 는 구조체 배열입니다. 이 구조체에는, isExsited (arr 의 배열 요소 값이 존재하는지 여부를 True / False 로 나타냄) 와 value (arr 의 배열 요소 값) 와 firstIndex (arr 의 배열 요소 값이 가장 먼저 나타나는 배열의 위치) 를 멤버로 취하고 있습니다. 

해당 요소를 살펴보고, elements 에서 그 요소 번째의 isExisted 를 살펴보고 이것이 False 이면, True 로 변경하고, value 에는 arr 의 요소를 저장하고, firstIndex 에는 arr 의 요소가 발견된 위치를 저장합니다.

일단, arr 의 첫 요소인 1 을 살펴봅니다. 그 1 을 elements 의 위치로 삼아서, elements[1] 의 isExisted 를 확인합니다. 이것이 False 이기 때문에 True 로 변경하고 (1 이 처음 출현했다는 의미) value 에는 1 을 저장하고, firstIndex 에는 arr 에서 1 이 처음 나타난 위치인 0 을 저장합니다.

앞서, arr[0] 의 처리가 끝이 났으니, 그 다음 번째인 arr[1] 의 요소로 넘어갑니다.

arr[1] 인 3 을 살펴봅니다. elements[3] 의 isExisted 를 확인합니다. 이것이 False 이기 때문에 True 로 변경하고 (3 이 처음 출현했다는 의미) value 에는 3 을 저장하고, firstIndex 에는 arr 에서 3 이 처음 나타난 위치인 1 을 저장합니다.

그 다음 번째인 arr[2] 의 요소로 넘어갑니다.

arr[2] 인 4 를 살펴봅니다. elements[4] 의 isExisted 를 확인합니다. 이것이 False 이기 때문에 True 로 변경하고 (4 가 처음 출현했다는 의미) value 에는 4 를 저장하고, firstIndex 에는 arr 에서 4 가 처음 나타난 위치인 2 을 저장합니다.

그 다음 번째인 arr[3] 의 요소로 넘어갑니다.

arr[3] 인 1 을 살펴봅니다. elements[1] 의 isExisted 를 확인합니다. 이것이 True 이기 때문에 (이미 1 이 출현했다는 의미) 아무 처리도 하지 않고 다음으로 넘어갑니다.

그 다음 번째인 arr[4] 의 요소인 7 부터 끝까지 위와 같은 과정을 반복합니다.

끝까지 반복하면 최종적으로, elements 배열에는 기존 배열에서 중복이 제거된 요소들 위치에 있는 데이터들만 세팅되어 있는 것을 확인할 수 있습니다.

이제 elements 를 정렬할 차례입니다. 먼저, isExisted 가 True 인 요소를 앞에 위치시키고, isExisted 가 False 인 요소는 뒤에 위치시킵니다. 단, isExisted 가 True 로 같은 경우에는, firstIndex 가 작은 요소를 앞에 위치시키고, 큰 요소를 뒤에 위치시킵니다. 이렇게 정렬하는 이유는, 중복 제거된 요소들이 기존의 arr 배열에서의 저장된 순서를 그대로 유지하기 위함입니다.

정렬이 끝났으면, 마지막으로, elements 에서 isExisted 가 True 인 요소들을 처음부터 끝까지 순서대로 다시 arr 배열에 저장합니다. (물론, 저장하기 전에, arr 배열을 초기화합니다.)

최종적으로, arr 배열에는 중복이 제거된 요소들이 저장되게 됩니다.

이제 소스 코드를 살펴보겠습니다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

enum{
	False = -1, True = 1
};

typedef struct _element{
	int isExisted;
	int value;
	int firstIndex;
}Element;

#define ARR_CAPACITY 10
#define ELEMENTS_CAPACITY 10

void DeleteDuplicatedElementsInArr(int* arr, int arrCapacity, Element* elements, int elementsCapacity, int* elementsCount);
void CopyArr(int* arr, int elementsCount, Element* elements);
void PrintArr(int* arr, int elementsCount);
int CompareElements(const void* one, const void* other);

int main(int argc, char* argv[]){
	int elementsCount = ARR_CAPACITY;
	int arr[ARR_CAPACITY] = { 1, 3, 4, 1, 7, 2, 5, 4, 3, 9 };
	Element elements[ELEMENTS_CAPACITY + 1];
	printf("중복 값 제거 전의 정수 배열\n");
	PrintArr(arr, elementsCount);
	printf("\n중복 값 제거 후의 정수 배열\n");
	DeleteDuplicatedElementsInArr(arr, ARR_CAPACITY, elements, ELEMENTS_CAPACITY, &elementsCount);
	qsort(elements, ELEMENTS_CAPACITY, sizeof(Element), CompareElements);
	CopyArr(arr, elementsCount, elements);
	PrintArr(arr, elementsCount);
	return 0;
}

void DeleteDuplicatedElementsInArr(int* arr, int arrCapacity, Element* elements, int elementsCapacity, int* elementsCount){
	int i;
	*elementsCount = 0;
	memset(elements, False, sizeof(elements[0]) * (elementsCapacity + 1));
	for (i = 0; i < arrCapacity; i++){
		if (elements[arr[i]].isExisted == False){
			elements[arr[i]].isExisted = True;
			elements[arr[i]].value = arr[i];
			elements[arr[i]].firstIndex = i;
			(*elementsCount)++;
		}
	}
}

void CopyArr(int* arr, int elementsCount, Element* elements){
	int i;
	memset(arr, 0, sizeof(arr[0]) * elementsCount);
	for (i = 0; i < elementsCount; i++){
		arr[i] = elements[i].value;
	}
}

void PrintArr(int* arr, int elementsCount){
	int i;
	for (i = 0; i < elementsCount; i++){
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int CompareElements(const void* one, const void* other){
	Element* oneElement = (Element*)one;
	Element* otherElement = (Element*)other;
	int basis = otherElement->isExisted - oneElement->isExisted;
	if (basis == 0){
		return oneElement->firstIndex - otherElement->firstIndex;
	}
	else{
		return basis;
	}
}

1 ~ 3 라인

프로그램 작성에 필요한 헤더파일들입니다.

5 ~ 7 라인

열거형 상수로 False 는 -1, True 는 1 로 정의하였습니다.False 를 0 이 아닌, -1 로 지정한 이유는, 코드의 통일성을 위해서 이렇게 정의하였습니다. 추후, 관련 코드가 나오면, 더 설명드리겠습니다.

9 ~ 13 라인

Element 라는 구조체를 정의하고 있습니다. 멤버로는 isExisted (배열 요소가 존재하는 지 여부), value (배열 요소 값), firstIndex (배열 요소가 처음으로 나타난 위치) 를 가지고 있습니다.

15 ~ 16 라인

arr (기존 배열) 와 elements (중복 제거하기 위해 중간에 사용할 배열) 의 크기를 각각 10 으로 지정하기 위한 매크로를 정의합니다.

18 ~ 21 라인

추후 사용될 함수들의 선언부입니다.

25 라인

arr 라는 배열을 임의의 정수로 초기화합니다.

26 라인

elements 라는 구조체 배열을 선언합니다.

28 라인

PrintArr 함수를 호출하여 arr 의 내용을 모두 출력합니다. (중복 제거되기 전의 요소들)

30 라인

DeleteDuplicatedElementsInArr 함수를 호출하여, arr 라는 배열에서 중복된 요소들을 제거하여 elements 라는 배열에 저장합니다. 맨 마지막 매개변수로 elementsCount 변수의 주소를 넘기는 이유는, 중복이 제거되고 나면 개수가 변경될 수 있기 때문입니다.

31 라인

중복이 제거된 배열인 elements 를 위의 알고리즘에서 설명한대로,정렬하기 위해 qsort 함수를 호출합니다. 이 때 정렬 기준을 설정하기 위해 CompareElements 라는 함수 포인터를 매개변수로 넘겨줍니다.

32 라인

정렬이 완료된 elements 배열을 CopyArr 함수를 호출하여 차례대로 다시 arr 배열에 저장합니다.

33 라인

PrintArr 함수를 호출하여 중복 제거가 완료된 arr 의 모든 요소들을 출력합니다.

37 라인

DeleteDuplicatedElementsInArr 함수의 정의부입니다. arr 배열과 arrCapacity (arr 의 크기), elements 배열과 elementsCapacity (elements 의 크기), elementsCount (elements 에 저장되는 요소의 개수) 를 매개변수로 받습니다. 이 때 elementsCount 변수를 주소로 받은 이유는 이 값이 main 함수가 아닌 DeleteDuplicatedElementsInArr 함수 내에서 변경될 것이기 때문입니다. 이 함수에서는, 중복 제거된 요소를 elements 에 저장하게 됩니다.

39 라인

elementsCount 를 0 으로 초기화합니다.

40 라인

elements 배열을 False (= -1) 로 초기화합니다. 0 이 아닌, -1 로 초기화 하는 이유는, firstIndex 가 최소 0 이 저장될 수 있기 때문에, 0 이 아닌 -1 로 미리 저장을 하는 것입니다. 

41 ~ 48 라인

arr 를 끝까지 돌면서, elements 의 arr[i] 번째의 isExisted 가 False 이면 isExisted 를 True 로 설정하고, value 에 arr[i] 를 저장하고, firstIndex 에는 i 를 저장합니다. 마지막으로, 요소를 하나 저장했으니, elementsCount 를 증가시킵니다.

51 라인

CopyArr 함수의 정의부입니다. 매개변수로 arr 배열과 elementsCount (elements 의 요소의 개수), elements 배열을 받고 있습니다. 이 함수는 elements 배열의 요소들을 arr 로 복사하는 역할을 합니다.

53 라인

복사하기 전에 먼저, arr 배열을 0 으로 초기화합니다.

54 ~ 56 라인

elementsCount 만큼 반복하면서, elements[i].value 를 arr[i] 에 저장합니다.

59 라인

PrintArr 함수의 정의부입니다. 이 함수는 arr 배열과 elementsCount (elements 배열 요소의 개수) 를 매개변수로 받아서 arr 배열의 요소를 elementsCount 만큼 출력합니다.

61 ~ 64 라인

elementsCount 만큼 반복하면서 arr[i] 를 출력합니다.

67 라인

CompareElements 함수의 정의부입니다. 매개변수로 one, other 라는 const void* 를 받고 있습니다. 이 함수는 qsort 시 정렬 기준이 되는데 사용되는 함수입니다. 두 요소를 비교하는 기준을 제시해 줍니다. 기본적으로, 반환값이 양수이면 두 요소를 교환하게 되어 있습니다. 먼저, isExisted 를 비교하고 (True 인 요소가 앞으로 오도록) 이 값이 같으면, firstIndex 를 비교하여 firstIndex 가 작은 요소가 앞으로 오도록 정렬 기준을 제시하고 있습니다.

68 ~ 69 라인

void* 이기 때문에, Element* 로 형변환합니다.

70 라인

먼저, 두 요소의 isExisted 를 비교합니다. other 에서 one 을 빼는 이유는, other (뒤 요소) 의 isExisted 가 True 인 경우 이를 앞으로 교환하게 하기 위함입니다. 즉, one 의 isExisted 가 False 이고, other 의 isExisted 가 True 이면, 이는 양수값이 되므로 교환이 되게 됩니다. (True 가 앞으로 오도록)

71 ~ 75 라인

만약 isExisted 가 True 로 같다면, firstIndex 로 2 차 비교를 합니다. 이는 작은 값이 앞으로 오도록 one 에서 other 의 firstIndex 를 뺍니다.

[실행 결과]

---

(qsort 함수 설명 참고)

https://msdn.microsoft.com/en-us/library/aa272872(v=vs.60).aspx

(memset 함수 설명 참고)

https://msdn.microsoft.com/en-us/library/aa246471(v=vs.60).aspx