[자료구조] 간단한 이차문제 선형으로 해결하기 (속도향상의 간단 예)

배열의 중복 값이 있는지 확인하는 함수를 만든다고 해보자. 가장 먼저 떠오리는 방법은 중첩 for문을 이용하는 것이 아닐까 싶다.

bool hasDuplicateVal(int* list, unsigned int len)
{
	for (int i=0; i<len; i++)
		for (int j = 0; j < len; j++)
		{
			if (i != j && list[i] == list[j])
				return true;
		}

	return false;
}

이 코드는 잘 동작하지만 비효율적이다. N * N 단계가 필요하다.

이 부분을 선형적으로 바꿔 보자. 배열이 가지는 범위를 정하고 range라는 추가 정보를 만들자.

bool hasDuplicateVal2(int* list, unsigned int len, unsigned int range)
{
	bool *existInt = new bool[range + 1];
	memset(existInt, 0, sizeof(existInt));

	for (int i = 0; i < len; i++)
	{
		int val = list[i];
		if (existInt[val])
		{
			delete existInt;
			return true;
		}
		else
			existInt[val] = true;
	}

	delete existInt;
	return false;
}

검색하는 동안 찾은 데이터를 기록해 두면 일일이 검색할 필요가 없게 된다. 물론 데이터의 range를 정확하게 알 때 더 유용할 것 같다.

search_duplicate.zip

0.02MB