[C++] 중복 처리 (1)

중복 처리

개요

　지난번에 업로드된 게시글에서는 다양한 난수 생성 방법들을 알아보았다. 이러한 난수를 활용하여 시스템을 설계하게 되면, 중복 문제가 불가피하게 발생할 수 있다. 특히 무작위로 고유한 값을 생성하거나 선택하는 과정에서 중복은 예기치 않은 오류를 발생시킬 수 있다. 따라서 중복 처리는 이러한 시스템에서 필수적인 단계가 되어야 한다.

　이번에는 난수 생성 시 발생하는 중복 문제와 그를 효과적으로 해결하는 방안들에 대해 살펴볼 예정이다. 특히, 중복된 값 자체의 처리와 중복 인덱스 처리, 이 두 가지 주제에 초점을 맞추어 알아보도록 하겠다.

---

본문

중복 제거

std::vector<int> v = { 7, 7, 1, 2, 3, 5, 5, 2, 8 };

　다음과 같이 vector 배열에 중복된 값이 있다고 가정해 보자. 이러한 값을 지우려면, 원소의 순서를 유지해야 하는지, 아니면 유지하지 않아도 되는지가 중요하다. 먼저 순서를 유지하지 않아도 되는 경우엔, 대표적으로 vector 클래스의 함수인 std::erase() 함수와 std::unique() 함수를 이용하는 방법이 있다.

 

출처: cppreference

 

　std::erase() 함수는 주어진 범위의 원소들을 벡터에서 제거하는 함수다. 이때 벡터의 크기가 실제로 줄어든다. std::unique() 함수는 연속적으로 중복된 원소들을 벡터의 끝으로 밀어내고, 중복된 원소들이 시작되는 위치를 가리키는 반복자를 반환한다. 

 

　결과적으로 std::unique()는 중복 원소들을 찾아 벡터의 끝으로 밀어내고, std::erase()는 그 중복 원소들을 실제로 제거하는 역할을 한다. 이 두 함수를 조합하여 중복된 값을 효과적으로 벡터에서 제거할 수 있다. 해당 알고리즘은 O(nlogn) + O(n) + O(n) = sort() + unique() + erase() = O(nlogn)이 된다. 이때 erase()의 시간 복잡도는 최악의 경우임을 고려하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>

template <typename T>
void PrintVector(std::vector<T> v)
{
	for (const T& val : v)
		std::cout << val << ' ';
	std::cout << "\n";
}

int main()
{
	std::vector<int> v = { 7, 7, 1, 2, 3, 5, 5, 2, 8 };
	std::sort(v.begin(), v.end());
	PrintVector(v);

	auto unique_v = std::unique(v.begin(), v.end());
	v.erase(unique_v, v.end());
	PrintVector(v);

	return 0;
}

출력

 

출처: cppreference

 

　두 번째로, 중복을 지원하지 않는 컨테이너를 활용하는 방법이다. 이를 테면, 일반적으로 균형 이진 검색 트리를 기반으로 하는 std::set 컨테이너를 이용하는 방법이다. 해당 컨테이너는 key만 저장하는데, 이때 각 원소가 고유한 키 값만을 가지기 때문에 중복을 제거할 때 사용하기 용이하다.

 

#include <iostream>
#include <vector>
#include <set>

int main()
{
	std::vector<int> v = { 7, 7, 1, 2, 3, 5, 5, 2, 8 };
	std::set<int> s(v.begin(), v.end());

	for (const auto& val : s)
		std::cout << val << ' ';

	return 0;
}

출력

 

　해당 알고리즘은 벡터의 모든 원소를 삽입할 때 O(nlogn)의 시간 복잡도를 갖는다. 만약 원소의 범위가 제한적일 경우 해시 기반의 자료구조인 std::unordered_set을 활용하면 O(n)의 시간 복잡도로 중복을 제거할 수 있다. 하지만 이 방법은 해시 충돌이 발생하지 않거나, 내부적으로 해시 테이블이 재해싱되지 않는 경우엔 원래의 순서가 유지되는 것처럼 보이게 되므로, 순서가 보장되지 않아도 될 때만 사용해야 한다.

 

#include <iostream>
#include <vector>
#include <unordered_set>

int main() {
    std::vector<int> v = {7, 7, 1, 2, 3, 5, 5, 2, 8};
    std::unordered_set<int> s(v.begin(), v.end());

    v.assign(s.begin(), s.end());  // 중복이 제거된 값을 다시 벡터에 할당

    for (const auto& val : v) 
        std::cout << val << ' ';

    return 0;
}

출력

---

출처: cppreference

 

　이제 기존 원소들의 순서를 유지하며 중복을 제거하는 방법을 알아보자. 먼저 기존에 존재하는 vector에서 본 원소를 std::unordered_set을 사용하여 추적하여, std::remove_if를 사용한 후 중복 원소를 벡터 끝으로 이동시키는 방법이다. std::remove_if()는 특정 조건을 만족하는 원소를 배열의 끝으로 이동시키고, 이동된 원소들 바로 다음 위치를 가리키는 반복자를 반환하는 함수다. 

 

#include <iostream>
#include <vector>
#include <unordered_set>

template <typename T>
void PrintVector(std::vector<T> v)
{
    for (const T& val : v)
        std::cout << val << ' ';
    std::cout << std::endl;
}

int main() 
{
    std::vector<int> v = { 7, 7, 1, 2, 3, 5, 5, 2, 8 };
    std::unordered_set<int> seen;

    auto end = std::remove_if(v.begin(), v.end(), [&seen](const int value) {
        return !seen.insert(value).second;
        });
    v.erase(end, v.end());
    
    PrintVector(v);
    
    return 0;
}

출력

 

　이미 처리된 원소를 추적하는 해시 세트 seen을 캡처하여, 원소가 이미 세트에 있을 경우 false를 반환한다. 따라서 벡터 내의 중복 원소는 true를 반환하고, 이 원소들을 벡터의 끝으로 이동시킨 후, std::remove_if에 의해 반환된 end 반복자부터 배열의 끝까지 모든 원소를 제거하면 순서를 유지하며 중복을 제거할 수 있다. 

　해당 알고리즘은 벡터의 모든 원소를 순회(O(n))하며 해시에 값을 삽입(O(1))한 후, 지정된 범위의 원소를 제거(O(n))하므로, 전체 연산의 시간 복잡도는 O(n)이다.

 

#include <iostream>
#include <vector>
#include <unordered_set>

template <typename T>
void PrintVector(std::vector<T> v)
{
    for (const T& val : v)
        std::cout << val << ' ';
    std::cout << std::endl;
}

int main() 
{
    std::vector<int> v = { 7, 7, 1, 2, 3, 5, 5, 2, 8 };
    std::unordered_set<int> seen;
    std::vector<int> result;

    for (const auto& num : v) 
    {
        if (seen.insert(num).second) 
            result.push_back(num);
    }

   	PrintVector(result);
}

　이번에는 람다 함수를 활용하지 않고, 직접 원소를 순회하며 중복된 원소를 확인하고 결과 벡터에 삽입하는 방법이다. 해당 알고리즘의 시간 복잡도 또한 O(n)다.

---

요약

중복 처리 (중복된 값 제거)
1. 순서가 보장되지 않아도 되는 경우
　- std::set 컨테이너를 이용하거나, 배열을 정렬한 후, std::erase(), std::unique() 함수를 이용하는 방법
2. 순서가 보장되어야 하는 경우
　- std::unordered_set 컨테이너를 이용해 이미 본 원소를 추적하고, 중복되지 않은 원소만 결과 벡터에 추가하는 방법