이진 검색 트리(1) - 이중 우선순위 큐, 보석 도둑

https://www.youtube.com/watch?v=IKnjzmyk70U&t=999s

0X16강 이진 검색 트리

---

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/stl_example.cpp

#include <bits/stdc++.h>
using namespace std;

void set_example(){
  set<int> s;
  s.insert(-10); s.insert(100); s.insert(15); // {-10, 15, 100}
  s.insert(-10); // {-10, 15, 100}
  cout << s.erase(100) << '\n'; // {-10, 15}, 1
  cout << s.erase(20) << '\n'; // {-10, 15}, 0
  if(s.find(15) != s.end()) cout << "15 in s\n";
  else cout << "15 not in s\n";
  cout << s.size() << '\n'; // 2
  cout << s.count(50) << '\n'; // 0
  for(auto e : s) cout << e << ' ';
  cout << '\n';
  s.insert(-40); // {-40, -10, 15}
  set<int>::iterator it1 = s.begin(); // {-40(<-it1), -10, 15}
  it1++; // {-40, -10(<-it1), 15}
  auto it2 = prev(it1); // {-40(<-it2), -10, 15}
  it2 = next(it1); // {-40, -10, 15(<-it2)}
  advance(it2, -2); // {-40(<-it2), -10, 15}
  auto it3 = s.lower_bound(-20); // {-40, -10(<-it3), 15}
  auto it4 = s.find(15); // {-40, -10, 15(<-it4)}
  cout << *it1 << '\n'; // -10
  cout << *it2 << '\n'; // -40
  cout << *it3 << '\n'; // -10
  cout << *it4 << '\n'; // 15
}

void multiset_example(){
  multiset<int> ms;
  // {-10, 15, 100}
  ms.insert(-10); ms.insert(100); ms.insert(15); // {-10, -10, 15, 15, 100}  
  ms.insert(-10); ms.insert(15);
  cout << ms.size() << '\n'; // 5
  for(auto e : ms) cout << e << ' ';
  cout << '\n';
  cout << ms.erase(15) << '\n'; // {-10, -10, 100}, 2
  ms.erase(ms.find(-10)); // {-10, 100}
  ms.insert(100); // {-10, 100, 100}
  cout << ms.count(100) << '\n'; // 2
  auto it1 = ms.begin(); // {-10(<-it1), 100, 100}
  auto it2 = ms.upper_bound(100); // {-10, 100, 100} (<-it2)
  auto it3 = ms.find(100); // {-10, 100(<-it3), 100}
  cout << *it1 << '\n'; // -10
  cout << (it2 == ms.end()) << '\n'; // 1
  cout << *it3 << '\n'; // 100
}

void map_example(){
  map<string, int> m;
  m["hi"] = 123;
  m["bkd"] = 1000;
  m["gogo"] = 165; // ("bkd", 1000), ("gogo", 165), ("hi", 123)
  cout << m.size() << '\n'; // 3
  m["hi"] = -7;  // ("bkd", 1000), ("gogo", 165), ("hi", -7)
  if(m.find("hi") != m.end()) cout << "hi in m\n";
  else cout << "hi not in m\n";
  m.erase("bkd"); // ("gogo", 165), ("hi", 123)
  for(auto e : m)
    cout << e.first << ' ' << e.second << '\n';
  auto it1 = m.find("gogo");
  cout << it1->first << ' ' << it1->second << '\n'; // gogo 165
}

int main(){
	set_example();
	multiset_example();
	map_example();
}

---

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

STL 사용법을 익힐 수 있게 도와준 문제였다. n이 0일 경우에 최솟값을 지우는 줄 알았는데 -1이였어서 이 부분에서 좀 틀렸었다.

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T; cin>>T;
    while(T--){
        multiset<int> ms;
        int k; cin>>k;
        while(k--){
            char c; int n;
            cin>>c>>n;
            if(c == 'I') ms.insert(n);
            if(c == 'D'){
                if(ms.empty()) continue;
                if(n==1) ms.erase(prev(ms.end()));   
                if(n==-1) ms.erase(ms.begin());
            }
        }
        if(ms.empty()) cout<<"EMPTY\n";
        else cout<<*prev(ms.end())<<' '<<*ms.begin()<<'\n';
    }
    return 0;
}

---

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

가방에 보석 한 개만 담을 수 있다는 것을 보았으면 풀었을 것 같은데... 좀 아쉬웠다.

이 문제의 풀이는 다시 한 번 봐야 귀류법부터 그 과정을 완전히 이해할 수 있을 것 같다.

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x16/1202.cpp

#include <bits/stdc++.h>
using namespace std;

int n,k;
pair<int,int> jewel[300003];
multiset<int> bag;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    //무게(second) 가격(first) 순으로 입력받음
    for(int i=0;i<n;i++) cin>>jewel[i].second>>jewel[i].first;
    sort(jewel,jewel+n);
    for(int i=0;i<k;i++){
        int c; cin>>c; bag.insert(c);
    }
    long long ans=0;
    for(int i=n-1;i>=0;i--){ //가격이 제일 높은 보석부터 확인
        auto it = bag.lower_bound(jewel[i].second); //보석을 담을 수 있는 가방을 찾음
        if(it==bag.end()) continue;
        ans+=jewel[i].first;
        bag.erase(it); //가방에는 한 개의 보석만 넣을 수 있으므로 가방을 삭제
    }
    cout<<ans;
    return 0;
}