04. 탐욕법 - 예제3

[1. 문제 설명]

 

 

[2. 풀이 접근]

적당한 사람을 배정 해야 할 때

vector 를 정렬해서 사용했을 시 문제점

 

탐색은 O(logn) 이 가능하나,

배정했으므로 vector 에서 제거해야 한다.

 

이 때, vector 특성 상 제거하는데, O(n) 시간이 소요된다.

 

이진검색트리인 set 혹은 multiset 을 사용한 경우

탐색과 제거 모두 O(logn) 에 할 수 있다.

 

그런데 set 은 중복 값을 저장 할 수 없으나

multiset 은 중복 값을 저장 할 수 있다.

 

 

[3. 코드]