문제
백준 7662번
multiset
multiset을 사용하면 쉽게 풀 수 있는 문제이다. 처음으로 set에 대한 개념을 알게 된 문제였다.
multiset은 c++의 STL이며 set container와 달리 key가 중복 가능한 set을 구현할 수 있다. multiset헤더가 아닌 set헤더를 통해 사용하는 것을 주의하자.
1
2
3
| #include <set>
multiset<int> ms;
|
- 트리 자료구조이다.
- multiset에 원소를 넣으면 자동으로 오름차순 정렬이 된다.
- 중위 순회로 원소에 접근한다. (중위 순회는 트리에서 루트 노드를 중간순서에 방문하는 순회)
- insert() 함수를 통해 원소를 삽입한다.
- erase() 함수를 통해 원소를 삭제할 수 있다. (erase함수 안에 인자로 값을 직접 넣으면 해당 값을 가진 모든 원소가 삭제 된다. 하지만 주소 값을 넣으면 그 주소에 해당 된 원소만 삭제된다.)
1
2
3
4
5
| multiset<int> ms;
ms.insert(3); // multiset에 3 삽입 {3}
ms.insert(4); // multiset에 3 삽입 {3,4}
ms.erase(ms.begin()); // multiset에서 시작 값(최소값) 삭제 {4}
|
- begin(), end()함수를 통해 가장 작은 값과 큰 값에 접근할 수 있다.
1
2
3
4
5
| int min,max;
min = *ms.begin();
auto iter = ms.end(); //반복자 생성
iter--; // end는 원소 끝 다음의 주소를 반환하므로 1을 빼준다.
max = *iter;
|
- upper_bound(), lower_bound() 함수를 통해 특정 원소가 시작되는 지점과 끝나는 지점을 알 수 있다.
- count() 함수를 통해 원소의 개수를 셀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| multiset<int> ms;
ms.insert(1);
ms.insert(2);
ms.insert(2);
ms.insert(3);
ms.insert(4);
// {1,2,2,3,4}
multiset<int>::iterator start,end;
start = ms.lower_bound(2);
end = ms.upper_bound(2);
cout<<*start; // 출력 : 2
cout<<*end; // 출력 : 3
cout<<ms.count(2); // 출력: 2
cout<<ms.count(4); // 출력: 1
|
구현
push할 경우에는 그냥 multiset에 넣어주기만 하면 된다.
최대값을 pop할 때는 end() 함수를 통해 끝 값에 접근하여 erase() 함수를 통해 해당 주소의 값을 지워준다. 이 때 주의할 점은 end()함수는 가장 끝 값의 다음 주소값을 가리킨다는 점이다.
1
2
3
| auto iter = ms.end();
iter--;
ms.erase(iter);
|
최소값을 pop할 때도 begin()을 통해 최소값의 주소에 접근하고 erase() 함수를 사용한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <iostream>
#include <set>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
int n;
while (t--)
{
cin >> n;
char order;
int num;
multiset<int> ms;
while (n--)
{
cin >> order >> num;
if (order == 'I')
{
ms.insert(num);
}
else
{
if (!ms.empty() && num == -1)
{
ms.erase(ms.begin());
}
else if (!ms.empty() && num == 1)
{
auto iter = ms.end();
iter--;
ms.erase(iter);
}
}
}
if (ms.empty())
{
cout << "EMPTY" << '\n';
}
else
{
auto end_iter = ms.end();
end_iter--;
cout << *end_iter << ' ' << *ms.begin() << '\n';
}
}
return 0;
}
|
