글 읽기 - c++ 우선순위 큐 질문 드립니다.

kyr9389 2년 전 0

우선순위 큐로 최소큐와 최대큐를 나누어 계산하고,

unordered_map을 이용하여 최소큐와 최대큐를 검증해줍니다.

마지막엔 값의 유무에 따라 최대/최소 값을 출력하게 해주었는데 20% 가량 채점되다가 틀려버리네요.

예제의 테스트 케이스와 질문게시판에 있는 반례들을 모두 넣어봤는데 정상적으로 나와서 어디가 문제인지 못찾고 있습니다.

혹여 반례나 잘못된 점을 알려주시면 정말 감사하겠습니다.

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	int t, n;
	long long value;
	priority_queue<long long> max_q;
	priority_queue<long long, vector<long long>, greater<long long>> min_q;
	unordered_map<long long, int> m;
	char cmd;
	cin >> t;
 
	for(int i = 0; i<t; i++) {
		
		int size = 0;
		
		while(!min_q.empty()) {
			min_q.pop();
		}
		while(!max_q.empty()) {
			max_q.pop();
		}
		
		m.clear();
		
		cin >> n;
		for(int j = 0; j<n; j++) {
			cin >> cmd >> value;
			
			if(cmd == 'D') {
				if(size > 0) {
					if(value == 1) {
						while(m[max_q.top()] == 0) {
							max_q.pop();
						}
						m[max_q.top()]--;
						max_q.pop();
					}else{
						while(m[min_q.top()] == 0) {
							min_q.pop();
						}
						m[min_q.top()]--;
						min_q.pop();
					}
					size--;
				}
				
				if(size == 0) {
					while(!min_q.empty()) {
						min_q.pop();
					}
					while(!max_q.empty()) {
						max_q.pop();
					}
				}
			}
			else {
				max_q.push(value);
				min_q.push(value);
				size++;
				
				if(m[value]) m[value]++;
				else m[value] = 1;
				
				// cout << "m[" << value << "] = " << m[value] << '\n';
			}
		}
		
		if(size == 0) cout << "EMPTY" << '\n';
		else cout << max_q.top() << " " << min_q.top() << '\n';
	}
}

siathus 2년 전 0

안타깝네요... 화이팅!

kyr9389 2년 전 0

multiset을 이용하여 해결했습니다. 앞뒤에서 삽입 삭제가 가능한 컨테이너가 있었네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 우선순위 큐 질문 드립니다.

kyr9389 2년 전 0

siathus 2년 전 0

kyr9389 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말