[3] [Class 3] - 백준 7662 이중 우선순위 큐

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

양쪽 방향으로 큐를 만족시키면서 중복된 값을 넣을 수 있어야 해서

깔끔하게 multiset을 사용했다. 

 

multiset에 대한 설명은 다음 게시글에 자세히 나와 있습니다.

 

// 이중 우선순위 큐
// multiset 이용해서 해결
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  ll T, k, val;
  char m;
  cin >> T;

  while(T--){
    multiset<ll> s;

    cin >> k;

    for(int i = 0 ; i < k ; i++){
      cin >> m >> val;

      if(m == 'I'){
        s.insert(val);
      }

      else{
        if(s.empty()) continue;

        if(val == 1
        	auto iter = s.end();
        	iter--;
        	s.erase(iter);
        }
        else{
        	auto iter = s.begin();
        	s.erase(iter);
        }
      }
    }

    if(s.empty()) cout << "EMPTY" << '\n';
    else cout << *s.rbegin() << ' ' << *s.begin() << '\n';
  }

  return 0;
}

 

I면 set에 넣고, D면 set에서 빼면 되서 정말 간단하다.

중요한 부분은 s.erase 메소드이다.

erase 메소드에 Iterator를 넣으면 가르키는 하나의 값만 빠지고

값을 넣으면 동일한 모든 값이 빠진다. 

 

if(val == 1){
	s.erase(*s.rbegin());
}
else{
	s.erase(*s.begin());
}

제거하는 부분을 처음에 이렇게 구성했는데, 맞왜틀을 한 30분동안 외친것 같다.