[BOJ 1655] 가운데를 말해요

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

- 문제 요약

 

백준이가 정수를 하나씩 외칠 때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다.

만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

그냥 우선순위 큐를 사용해서 풀면 될 것 같습니다.

하지만 그냥 우선순위 큐를 하나만 선언해서 중간값을 구하다 보면 시간 복잡도가 터지게 됩니다.

그러므로 Max heap, Min heap 개념을 사용해서 문제를 푸는게 좋아 보입니다.

우선순위 큐를 2개 선언하고, 하나는 Max heap 전용, 하나는 Min heap 전용으로 두고 풀겠습니다.

Max heap 전용 큐는 mxpq, Min heap 전용 큐는 mnpq라고 하겠습니다.

 

mxpq.top()<=mnpq.top()인 상태를 유지하면서 값을 넣어줍니다.

만약 mxpq.top()>mnpq.top()인 경우에는 미리 선언해놓은 변수 두 개에 값을 넣어주고 후처리를 해줍니다.

 

 

- 코드 작성

 

 

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

typedef long long ll;
int n;
priority_queue<int>mxpq;
priority_queue<int,vector<int>,greater<int>>mnpq;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		if(mxpq.size()==0){
			mxpq.push(a);
		}
		else{
			if(mxpq.size()==mnpq.size()){
				mxpq.push(a);
			}
			else{
				mnpq.push(a);
			}
			if(mxpq.top()>mnpq.top()){
				int mx=mxpq.top();
				int mn=mnpq.top();
				mxpq.pop();
				mnpq.pop();
				mxpq.push(mn);
				mnpq.push(mx);
			}
		}
		cout<<mxpq.top()<<'\n';
	}
}

시간 복잡도 생각 안 하고 무지성으로 풀다가 이상함을 감지하고 바로 알고리즘 바꿨습니다.

다행스럽게도 1트만에 맞았습니다!! 떴네요 :D

 

코드 제출 결과