[백준 7662 c++] 이중 우선순위 큐

문제 링크

www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

문제 접근

// 접근: 이중 우선순위 큐-> 데크나 priority_que 맥스힙 민힙 해서 할라했으나 원소 삭제하는 데에서 막힘
// 접근2: AVL트리 자료형 set 이용해서 함 근데 중복이 안됨
// 접근 3: multiset 은 같은 균형잡힌 이진트리인데 중복허용

 

문제 풀이

// 풀이: multiset 이용해서 삽입시 자동 정렬, 삭제시 최대최소가 맨앞,맨뒤 원소

 

주의

// 주의: set 최신화 하는거 못보고 계속 틀림
// 주의: end() 주소로 계산할 때 -1안됨 -> 따로 변수로 저장하고 계산

// 주의: 마지막 cout할 때 <<'\n' 안해주면 백준 틀림!!!

개념

// 개념: multiset<int> ,set<int> 균형잡힌 이진 트리 중복허용, 불허용
// auto 자료형 자동 할당

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>

// [백준 7662 c++] 이중 우선순위 큐
// 접근: 이중 우선순위 큐-> 데크나 priority_que 맥스힙 민힙 해서 할라했으나 원소 삭제하는 데에서 막힘
// 접근2: AVL트리 자료형 set 이용해서 함 근데 중복이 안됨
// 접근 3: multiset 은 같은 균형잡힌 이진트리인데 중복허용
// 풀이: multiset 이용해서 삽입시 자동 정렬, 삭제시 최대최소가 맨앞,맨뒤 원소
// 주의: set 최신화 하는거 못보고 계속 틀림
// 주의: end() 주소로 계산할 때 -1안됨 -> 따로 변수로 저장하고 계산
// 개념: multiset<int> ,set<int> 균형잡힌 이진 트리 중복허용, 불허용
// auto 자료형 자동 할당
#define MAX 5000
using namespace std; // cin,cout 편하게 사용 라이브러리

int t;
int n;
int main()
{
	// IO 속도 향상
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t ; 

	for (int i = 0; i < t; i++)
	{
		multiset<int> s;// AVL 트리 

		cin >> n;
		for (int j = 0; j < n; j++)
		{
			char op;
			int num;
			cin >> op>> num;
			if (op == 'I')
			{
				s.insert(num);
			}
			else 
			{
				if (!s.empty()) // 원소가 존재하고 삭제명령이면)
				{
				// 최대값 삭제
					if (num == 1)
					{
						auto it = s.end(); // auto 자료형 자동 설정
						it--; // 이렇게 안하면 주소 바뀜
						s.erase(it);
					} //최소값 삭제
					else if (num == -1)
					{
						s.erase(s.begin());
					}
				}
			}
		}
		if (s.empty()) { cout << "EMPTY" << '\n'; }
		else {
			auto it = s.end();
			it--;
			cout << *(it) << " " << *(s.begin()) << '\n';
		}
	}
	
    return 0;
}