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

이번 시간에는, 정수 배열에서 중복 값 (요소) 을 제거하는 방법에 대해 설명드리고자 합니다. 참고로, 이 방법은 시간 복잡도 O(n2) 에 수행되는 알고리즘입니다. 소스코드 설명에 앞서, 알고리즘을 도식화해서 먼저, 설명드리겠습니다.

arr 는 기존의 정수 배열을 의미합니다. 이 배열에는, 중복된 정수값들이 무작위로 저장되어 있습니다. 편의상 배열의 크기는 10 으로 가정하겠습니다. 현재는, arr 배열에, 순서대로, 1, 3, 4, 1, 7, 2, 5, 4, 3, 9 값이 들어 있습니다. 그리고, uniqueArr 배열은 중복을 제거한 요소들을 임시로 담는데 사용할 배열입니다. 현재 이 배열에는 아무 값도 담겨 있지 않습니다.

arr 배열의 가장 좌측 요소인 1 부터 시작해서 끝까지 반복하면서, 차례대로 그 배열 요소 값이 uniqueArr 배열에 존재하는지 확인하고, 만약 존재하지 않는다면, uniqueArr 배열에 그 요소 값을 저장하고, 존재한다면, 저장하지 않습니다.

arr 의 가장 첫 요소인 1 을 uniqueArr 에서 검색한 결과가 없어서 1 을 저장합니다.

두번째 요소인 3 을 기준으로 uniqueArr 에 그 값이 존재하는지 검색을 진행합니다. 

uniqueArr 에 3 에 대한 검색 결과가 없기 때문에, 1 다음 오른쪽에 3 을 저장합니다.

이번에는, 4 에 대해서 uniqueArr 에서 검색을 진행합니다.

역시 uniqueArr 에 4 에 대한 검색 결과가 없기 때문에 4 를 저장합니다.

이번에는, 1 을 uniqueArr 에서 검색을 진행합니다.

이번에는 1 을 uniqueArr 에서 검색해본 결과, 가장 좌측에 1 이 이미 있기 때문에, uniqueArr 에 1 을 또 저장하지 않습니다. (즉, 중복을 제거한 것입니다.)

지금까지와 같은 과정을 7 부터 배열의 마지막 요소인 9 까지 반복합니다.

그러면, 최종적으로, uniqueArr 배열에 1, 3, 4, 7, 2, 5, 9 가 순서대로 저장되게 되고, 이는 기존의 arr 배열에서 중복 값들을 제거한 형태입니다.

그리고는, uniqueArr 배열의 내용을 모두 기존 배열인 arr 에 복사합니다.

결과적으로, 기존 배열인 arr 에는 원래 들어 있던 정수 값들 중에서 중복된 값들이 제거된 형태로 저장되게 됩니다. 이를 소스 코드로 나타내 보겠습니다.

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

enum{
	False, True
};

#define ARR_CAPACITY 10

void DeleteDuplicatedElementsInArr(int* arr, int* arrCapacity);
int SearchKeyInArr(int* arr, int arrCapacity, int key);
void PrintArr(int* arr, int arrCapacity);

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

void DeleteDuplicatedElementsInArr(int* arr, int* arrCapacity){
	int* uniqueArr = (int*)calloc(*arrCapacity, sizeof(int));
	int uniqueArrCount = 0;
	int i;
	for (i = 0; i < *arrCapacity; i++){
		if (!SearchKeyInArr(uniqueArr, uniqueArrCount, arr[i])){
			uniqueArr[uniqueArrCount++] = arr[i];
		}
	}
	memset(arr, 0, sizeof(arr[0]) * (*arrCapacity));
	for (i = 0; i < uniqueArrCount; i++){
		arr[i] = uniqueArr[i];
	}
	if (uniqueArr){
		free(uniqueArr);
		uniqueArr = NULL;
	}
	*arrCapacity = uniqueArrCount;
}

int SearchKeyInArr(int* arr, int arrCapacity, int key){
	int i;
	for (i = 0; i < arrCapacity; i++){
		if (arr[i] == key){
			return True;
		}
	}
	return False;
}

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

5 ~ 7 라인

열거형 상수로 False (= 0), True (= 1) 를 정의합니다.

9 라인

배열의 크기를 매크로로 정의합니다.

11 ~ 13 라인

소스코드에 사용되는 함수들의 선언부입니다.

16 라인

기존 배열인 arr 를 10 크기로 선언하고, 10 개의 임의의 정수들로 초기화합니다.

17 라인

arrCapacity 라는 변수를 선언하고 배열의 크기인 10 을 저장합니다.

19 라인

배열의 요소를 출력하는 함수인 PrintArr 함수를 호출합니다. 중복 값 제거 전의 정수 배열의 요소들이 출력됩니다.

20 라인

DeleteDuplicatedElementsInArr 라는 함수를 호출하여, arr 라는 배열에서 중복된 요소들을 제거합니다. 이 함수를 호출할 때는, arr 라는 배열을 넘기고, arrCapacity 변수의 주소값을 넘깁니다. 주소값을 넘기는 이유는, 이 함수 내에서 중복값이 제거되고 나면, arrCapacity 가 감소되어 변경될 수 있기 때문입니다.

22 라인

PrintArr 함수를 호출하여 중복 값 제거 후의 정수 배열의 요소들을 출력합니다.

26 라인

DeleteDuplicatedElementsInArr 함수의 정의부입니다. 이 함수는 매개변수로 기존 배열 (arr) 과 그 배열의 크기 (arrCapacity) 를 매개변수로 받습니다. arr 기존 배열에서 중복된 값을 제거하여 반환하는 함수입니다.

27 라인

uniqueArr 라는 중복 제거된 요소들이 임시로 저장될 배열을 동적할당 합니다. (calloc 함수 사용)

28 라인

uniqueArrCount 라는 변수를 선언하여 uniqueArr 배열에 저장된 요소의 개수를 관리합니다. 현재는, 아무것도 저장되어 있지 않기 때문에 0 을 저장합니다.

30 ~ 34 라인

arr 배열을 처음부터 끝까지 반복하면서, uniqueArr 에서 arr 배열의 요소를 검색하여 (SearchKeyInArr 함수 사용) 검색 결과가 없으면 uniqueArr 배열에 arr 배열의 요소를 저장합니다. 검색 결과가 있는 경우에는, 이미 저장된 것이기 때문에 다시 저장하지 않고 다음으로 넘어갑니다.

35 라인

중복 제거된 요소들이 모두 uniqueArr 에 저장되었을 테니, 이제는 memset 함수를 통해서, 기존 배열인 arr 의 모든 요소들을 0 으로 초기화합니다.

36 ~ 38 라인

uniqueArr 배열의 모든 요소들을 arr 배열에 복사합니다.

39 ~ 42 라인

uniqueArr 의 역할은 모두 끝났으니 할당해제합니다. (free 함수 사용)

43 라인

arrCapacity 의 값을 중복 제거된 요소의 개수로 변경합니다.

46 라인

SearchKeyInArr 함수의 정의부입니다. 이 함수는 매개변수로 임의의 배열 (arr), 배열의 크기 (arrCapacity), 검색할 키 값 (key) 을 받습니다. arr 배열에서 key 를 검색하여 존재하면 True 를, 없으면 False 를 반환합니다.

48 ~ 53 라인

배열의 모든 요소를 탐색하면서, key 를 찾으면 True 를 반환하고, 그렇지 않으면 False 를 반환합니다.

56 라인

PrintArr 함수의 정의부입니다. 매개변수로 배열 (arr), 배열의 크기 (arrCapacity) 를 받아서, 모든 배열의 요소를 출력합니다.

58 ~ 61 라인

배열의 모든 요소를 화면에 출력합니다.

[실행 결과]

---

( calloc 함수 설명 참고)

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

(memset 함수 설명 참고)

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

(free 함수 설명 참고)

https://msdn.microsoft.com/en-us/library/we1whae7.aspx