글 읽기 - 우선순위큐로 구현했는데,, 왜 틀렸을까요

cr3218 3년 전 1

중앙값을 구해주기 위해 minheap maxheap을 선언하였고,

maxheap의 size가 minheap의 size와 같거나(짝수개의 데이터일 경우)

1이 클 경우(홀수개의 데이터일 경우) 로 구현을 해주었습니다. 데이터를 받으면 중앙값이 항상 maxheap의 top에 있도록 처리해주고 값을 출력했는데

틀렸다고 뜨네요 ㅠㅠ 왜일까요!!

도와주세요

해결했습니다 한 부분에서 구현을 잘못했더군요!1

//틀린코드
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;


int main() {
	int t; scanf("%d", &t);
	priority_queue<int> maxheap;
	priority_queue<int,vector<int>,greater<int>> minheap;
	int a; 

	for (int i = 1; i <= t; i++) {
			scanf("%d", &a);
			if (maxheap.size()==0) {
				maxheap.push(a);
			}
			else if (minheap.size() == 0) {
				if (maxheap.top() > a) {
					minheap.push(maxheap.top());
					maxheap.pop();
					maxheap.push(a);
				}
				else {
					minheap.push(a);
				}
			}
			else if(minheap.size()>maxheap.size()){
				if (minheap.top() > a) {
					maxheap.push(a);
				}
				else {
					maxheap.push(minheap.top());
					minheap.pop();
					minheap.push(a);
				}
			}
			else if (maxheap.size()>minheap.size()) { //이 부분이 잘못됨
				if (minheap.top() > a) {
					minheap.push(maxheap.top());
					maxheap.pop();
					maxheap.push(a);
				}
				else {
					minheap.push(a);
				}

			}
			else {
				if (minheap.top() > a) {
					maxheap.push(a);
				}
				else {
					maxheap.push(minheap.top());
					minheap.pop();
					minheap.push(a);
				}
			}
			printf("%d\n",maxheap.top());
	}
}

//맞은코드
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;
void maxtomin(int a) {
	minheap.push(maxheap.top());
	maxheap.pop();
	maxheap.push(a);
}
void mintomax(int a) {
	maxheap.push(minheap.top());
	minheap.pop();
	minheap.push(a);
}
int main() {
	int t; scanf("%d", &t);
	int a;

	for (int i = 1; i <= t; i++) {
		scanf("%d", &a);
		if (maxheap.size() == 0) {
			maxheap.push(a);
		}
		else if (minheap.size() == 0) {
			if (maxheap.top() > a) maxtomin(a);
			else minheap.push(a);
		}
		else if (minheap.size() > maxheap.size()) {
			if (minheap.top() > a)	maxheap.push(a);
			else mintomax(a);
		}
		else if (maxheap.size() > minheap.size()) {
			if (maxheap.top() >= a) maxtomin(a);
			else  minheap.push(a);
		}
		else { //둘의 사이즈가 같다
			if (minheap.top() > a) maxheap.push(a);
			else mintomax(a);
		}
		printf("%d\n", maxheap.top());
	}
}

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

문제

문제

출처

ICPC

우선순위큐로 구현했는데,, 왜 틀렸을까요

cr3218 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말