JArchive 프로그래밍 일기

이중우선순위큐 문제링크 

리뷰 

최소값 삭제와 최대값 삭제를 위해 매번 큐의 정렬을 다시 할 수 는 없다. 그래서 우선순위큐 2개를 뒀다. 

우선순위큐의 기본 정렬은 less라서 오름차순이다. 

오름차순 정렬하는 최소값 큐 min_pq

내림차순 정렬하는 최대값 큐 max_pq 

큐 사이즈를 관리하는 변수가 0이 되면, 큐 2개 다 비워줘야하는데! 이 부분을 빠뜨려서 다른 분 코드를 참고했다. 

1. priority_queue 2개 사용한 코드 

#include <string>
#include <vector>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<>> min_pq;
priority_queue<int, vector<int>, less<>> max_pq;
int pq_size; // 큐의 사이즈 관리

vector<int> solution(vector<string> op) {
  vector<int> answer = {0, 0};

  for(auto s : op){
    string order = s.substr(0, 1); // 명령 문자 I 또는 D 

    int num = stoi(s.substr(2, s.size())); // 숫자부분  

    if(order == "I") {
      min_pq.push(num);
      max_pq.push(num);
      pq_size++;
    }
    else if(pq_size > 0 && order == "D"){

      (num == -1) ? min_pq.pop() : max_pq.pop();
      pq_size--;

      if(pq_size == 0){
        while(!min_pq.empty()) min_pq.pop();
        while(!max_pq.empty()) max_pq.pop();
      }
    }
  }

  if(!min_pq.empty() && !max_pq.empty()) answer = {max_pq.top(), min_pq.top()};
  return answer;
}

풀고 나니깐 다른 분들 코드에 set이 보이길래 multiset으로 풀어도 됬겠다 싶었다.  

2. vector 로 푼 코드 

앞, 뒤에서 하나씩 erase로 지워주기만 하면 되니까. vector로도 괜찮다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> op) {
  vector<int> answer = {0,0};
  vector<int> v;

  for(auto s : op){
    string order = s.substr(0, 1); // 명령
    int num = stoi(s.substr(2)); // 숫자

    if(order == "I") {
      v.push_back(num);
      sort(v.begin(), v.end(), greater<>()); // 푸시하고 바로 정렬.
    }
    else {
      if(v.size() == 0) continue;

      (num == -1) ? v.erase(v.end()-1) : v.erase(v.begin());
    }
  }

  if(!v.empty()) {
    answer.clear();
    answer = {v[0], v[v.size()-1]};
  }
  return answer;
}

문제 링크 

중복 원소를 오름차순으로 저장하는 multiset 으로 풀었다.  

원소를 지우기 전에, 사이즈를 꼭 체크하도록 하자..

다시 풀어볼 문제. 

"맞았습니다" 코드 링크 

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

int T, k, n;
char ch;

void solve(){

  multiset<int> ms;
  cin >> k;

  while(k--){
    cin >> ch >> n;
    if(ch == 'I') ms.insert(n);
    else if(ms.size() > 0){
      if(n > 0){ // 최댓값 삭제
        auto iter = ms.end();
        ms.erase(--iter);
      }else ms.erase(ms.begin());
    }
  }

  if(ms.size() == 0) cout << "EMPTY\n";
  else {
    auto iter = ms.end();  --iter;
    cout << *iter << ' ' << *ms.begin() << '\n';
  }
  return;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> T;
  while(T--){
    solve();
  }
  return 0;
}

multiset reference 

multiset 정리 포스팅