[BOJ알고리즘, C++]#7785_회사에 있는 사람, 연결 자료구조, Set 컨테이너 활용

 

[BOJ알고리즘, C++]#7785_회사에 있는 사람

 

BOJ 알고리즘 문제 풀이, 7785번 회사에 있는 사람

Set 컨테이너를 활용하는 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

1. 문제

 

#1. 풀이

1. Set 컨테이너

[Basic C++] #29_Set, MultiSet, STL 컨테이너

 

• STL의 Set 컨테이너는 균형 이진트리로 구현한 노드 기반의 연관 컨테이너입니다. Set 컨테이너는 Key 값을 원소로 이루어진 집합입니다. 이때, Set 컨테이너는 Key 값의 중복을 허용하지 않으며, 자동으로 "오름차순(Lees)" 정렬합니다. Set의 탐색은 중위순회를 활용합니다. Set 컨테이너는 Map 컨테이너와 달리, Key 값은 Key인 동시에 Value이기도 합니다.

 

2. Set의 정렬 기준 변경

#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;

bool Comparison(const int& a, const int& b)
{
	return a < b;
}

struct Comparison2
{
	bool operator()(const int& a, const int& b)
	{
		return a < b;
	}
};

int main()
{
	// #1. 빈 Set 생성
	set<int> s1;

	// #2. 초기화 리스트
	set<int> s2 = { 1, 2, 3 ,4 ,5 };
	set<int> s3{ 1, 2, 3, 4, 5 };

	// #3. 복사 상성자 혹은 다른 컨테이너를 활용한 범위 기반 초기화
	vector<int> v = { 1, 2, 3, 4 ,5 };
	set<int> s4(s1);
	set<int> s5(v.begin(), v.end());

	// #4. 정렬 방법 변경 : std::greater 함수 객체 활용
  	set<int, greater<int>> s6;

	s6.insert(3);
	s6.insert(1);
	s6.insert(5);

	for (const auto& val : s6)
		cout << val << endl;

	// #5. 정렬 방법 변경 : std::function 활용
	function<bool(const int&, const int&)> Comp = Comparison;
	set<int, function<bool(const int&, const int&)>> s7(Comp);

	// #6. 정렬 방법 변경 : struct(구조체) 활용
	set<int, Comparison2> s8;
	
	return 0;

}

 

Details

 

1. 빈 Set 생성을 위한 초기화 방법입니다.
2. 초기화 리스트를 활용하는 Set 초기화입니다.
3. 복사 생성자를 통해 기존의 Set 컨테이너를 복사할 수 있으며, 그리고 Set 컨테이너 외 다른 컨테이너를 통해 범위 기반 복사가 가능합니다.
4. C++ STL에서 제공하는 greater 함수 객체를 활용해, Set 컨테이너의 정렬 기준을 내림차순으로 변경 가능합니다.
5. <functional>에서 제공하는 function을 통해 일반화한 함수 객체를 활용할 수 있습니다.
6. struct(구조체)를 함수 객체처럼 활용하는 방법입니다. 구조체 내부에 연산자(operator())를 오버로딩해 해당 구조체를 함수처럼 호출할 수 있습니다.

 

3. Set의 삽입/삭제

#include <set>

s.clear()		: 모든 원소를 제거

s.insert(k)		: 새로운 원소 "K"를 삽입합니다. 성공 여부는 pair<iterator, bool>로 나옵니다.

s.insert(iter, k)	: iter(반복자)가 가리키는 위치부터 K를 삽입할 위치를 탐색하여 K를 삽입합니다.

s.erase(iter)		: iter가 가리키는 위치의 원소를 제거합니다.

s.erase(k)		: 특정 Key 값을 갖는 원소를 제거합니다.

s.erase(start, end)	: [start, end) 범위의 원소를 모두 제거합니다.

 

#2. 코드

1. 풀이 코드

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

int N;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    cin >> N;
    
    set<string, greater<string>> s;
    
    while(N--)
    {
        string name;
        string entrance;
        
        cin >> name >> entrance;
        
        if(entrance == "enter")
        {
            s.insert(name);
        }
        else
        {
            s.erase(name);
        }
    }
    
    for(const auto& name : s)
        cout << name << '\n';
    
}

 

Details

 

1. greater 함수 객체를 활용해서 Set 컨테이너의 정렬 기준을 디폴트 정렬(오름차순)에서 내림차순으로 변경하여 초기화합니다.
2. Insert(k)를 통해 Set 컨테이너에 새로운 키 값을 삽입합니다. 
3. erase(k)를 통해 Set 컨테이너에서 특정 키 값을 제거합니다.