Priority_queue

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14464 🧐 관찰 및 접근 # 소에 대해서는 끝나는 시간이 가장 빠른 소를, 닭에 대해서는 가장 $T$가 빨리 오는 닭을 쓰는 그리디가 성립한다. 이를 구현하는 방법은 여러가지가 있겠지만, 여기서는 multiset과 이분탐색을 이용하겠다. 💻 풀이 # 코드 (C++): void solve(){ int C, N; cin >> C >> N; multiset<int> chicken; rep(i, 0, C){ int x; cin >> x; chicken.insert(x); } vector<pii> cow(N); rep(i, 0, N) cin >> cow[i].first >> cow[i].second; sort(all(cow), [](pii a, pii b){ return a.second < b.second; }); int ans = 0; for(auto [s, e]: cow){ auto it = chicken.lower_bound(s); if(it != chicken.end() && *it <= e){ ans++; chicken.erase(it); } } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/11920 🧐 관찰 및 접근 # 배열 $[3, 4, 1, 2, 7, 6]$이 있다고 하자. 처음 한바퀴를 돌면 어떻게 되지? $[3, 1, 2, 4, 6, 7]$이 된다. 이걸 어떻게 해석할 수 있을까? 가장 큰 수는 맨 오른쪽에 고정된다. 다른 수들은, 오른쪽에 붙어있수가 자기보다 작은것들을 왼쪽으로 다 밀고, 오른쪽으로 간다. 오큰수? 스택? 그런맛인데 이거 두번하면 어떻게? $[1, 2, 3, 4, 6, 7]$이 된다. 나 5 안썼었구나 ㅋㅋ 이런 값을 두개정도 들고있다가..? 뭔가 그런느낌…? $K$번 진행한다고 하면, 값을 $K$개정도 들고있다가, 들고있는 값중 젤 작은거보다 작으면 그대로 통과시키고, 그것보다 크다면? 어떻게 되는거지? $[5, 7, 4, 3, 6, 8, 1, 2]$를 해보자. $[5, 4, 3, 6, 7, 1, 2, 8]$ $[4, 3, 5, 6, 1, 2, 7, 8]$ 두개 들고있다가 큰거 만나면 작은값 빼버려서 튀면 되는듯?? 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<int> A(N); rep(i, 0, N) cin >> A[i]; vector<int> ans; priority_queue<int, vector<int>, greater<int>> PQ; rep(i, 0, N){ PQ.push(A[i]); if(PQ.size() > K){ ans.push_back(PQ.top()); PQ.pop(); } } while(!PQ.empty()){ ans.push_back(PQ.top()); PQ.pop(); } for(auto x: ans) cout << x << " "; } 🔒 구현 코드 잠금