Unordered_set : 호다닥 찾아버리기(+BOJ 수찾기)

※docs.microsoft.com/ko-kr/cpp/standard-library/set?view=msvc-160docs.microsoft.com/ko-kr/cpp/standard-library/unordered-set?view=msvc-160

에서 더욱 자세히 살펴보실 수 있습니다.

 

 

해시를 매우면서 살펴본 map은 다음과 같은 강점이 있었습니다.

 

해시는 요소를 저장할 때 키값을 중점으로 레드-블랙 트리로 저장하기 때문에, 레드블랙 트리의 특징을 그대로 가져갑니다. 하지만 정렬과 연산을 매우 많이 해야 할 때는 O(nlogn)의 시간 자체가 부담스러울 수 있습니다.

 

그래서 우리는 unordered_set을 사용합니다. 이 클래스는 요소를 정렬하여 저장하지 않습니다. 또, 그 자체를 해시로 저장합니다. 따라서 삽입 삭제 검색을 할 때 O(1)시간 안에 요소를 다룰 수 있습니다(선형 충돌이 많은 경우, 최악의 경우에는 O(n)시간이 걸립니다).

 

[헤더 선언]

#include <unordered_set>

 

[선언]

unordered_set<[변수 타입]> [변수 명];

예를 들어, long 타입을 가지는 unoredered_set 변수 set를 선언하기 위해선 다음과 같이 선언하면 됩니다.

unordered_set<long> set;

 

[기능]

-삽입-

위에서 선언한 set변수에 temp를 넣는 방법은 다음과 같습니다.

long temp;
cin >> temp;

set.insert(temp);

각 요소는 이터레이터를 통해 접근할 수 있습니다. 

   unordered_set<char> c1;
   
   c1.insert('a');
   c1.insert('b');
   c1.insert('c');
   
   for (auto it : c1) {
    cout << "[" << it << "] ";
    }

[a][b][c]가 출력 됩니다. 이터레이터의 성질을 이용하여 원하는 대로 출력하면 되겠습니다.

 

-삭제-

이터레이터 위치의 요소를 erase를 통해 삭제할 수 있습니다. 

#include <unordered_set>
#include <iostream>
using namespace std;

int main()
{
    unordered_set<char> c1;

    c1.insert('a');
    c1.insert('b');
    c1.insert('c');
    c1.insert('d');
    c1.insert('e');
    c1.insert('f');

    
   unordered_set<char>::const_iterator it = c1.begin();
   c1.erase(it++);
   c1.erase(it);

   for (unordered_set<char>::const_iterator iter = c1.begin(); iter != c1.end(); ++iter)
   {
       cout << "[" << *iter << "] ";
   }

    return 0;
}

출력 결과

-검색-

find함수를 통해 검색할 수 있습니다. 검색하는 것이 없을 경우 iterator는 end()에 도달합니다.

#include <unordered_set>
#include <iostream>
using namespace std;

int main()
{
    unordered_set<char> c1;

    c1.insert('a');
    c1.insert('b');
    c1.insert('c');
    c1.insert('d');
    c1.insert('e');
    c1.insert('f');

    
    if (c1.find('a') != c1.end()) cout << "a is in unordered set\n";

    if (c1.find('z') == c1.end()) cout << "z is not in unordered set\n";
    return 0;
}

출력 결과

[문제 적용]

www.acmicpc.net/problem/1920

1920번: 수 찾기

일반적인 방법으로 시도하면 시간 초과를 면치 못합니다.

unordered_set의 해시 저장을 이용하여 빠르게 찾을 수 있습니다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <unordered_set>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	unordered_set<long> set;

	int n, m;

	cin >> n;
	for(int i=0; i<n; i++)
	{
		long temp;
		cin >> temp;

		set.insert(temp);
	}

	cin >> m;
	for(int j=0; j<m; j++)
	{
		long temp;
		cin >> temp;
		
		if (set.find(temp) == set.end())
		{
			cout << 0 << "\n";
		}
		else
		{
			cout << 1 << "\n";
		}
	}
	return 0;
}