#1655 가운데를 말해요

# 문제

* 시간 제한도 0.1초로 짧음

  단순하게 하나씩 비교하면서 풀면 시간이 더 오래 걸릴 것이기 때문에 우선순위 큐로 구현

  우선순위 큐는 힙(heap)을 가지고 구현할 수 있음

 

출처: https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

이거 보고 했었는데 제대로 안나와서

결국엔 문제자체를 구글링해서 풀었다ㅠㅠ

세시간 동안 뻘짓했네ㅋㅋㅋ

 

다시 제대로 읽고 풀어본다 일단 자기로 함ㅋㅋ

 

---

220508 문제 다시 풀어봄

문제를 완전 까먹고 있다가 어쩌다 보니까 이문제를 다시 풀게됐다

전에는 내가 그냥 위의 블로그 보고 풀기만 했지 백준에 제출은 안한 상태여서 풀었다고 체크가 안되어있어서

풀었던 문젠지 몰랐다ㅋㅋㅋ

 

처음에 제한시간이 0.1초길래 벡터를 써서 sort하면 시간이 오래 걸릴것 같았다

그래서 우선순위 큐를 써서 중간 인덱스를 받아올 생각이었는데

큐에는 하필 검색을위한 함수가 없어서;,,

근데 보다 보니까 예전에 봤던 문제같아서ㅋㅋㅋㅋ

이번엔 내가 직접 풀어보기로 했음

 

풀이

min, max 큐를 만들고 min은 내림차순으로 구현, max는 오름차순으로 구현한다

왜냐하면 min의 top은 min 중에 가장 큰 값이고, max의 top은 max 중에 가장 작은 값이기 때문에

이 둘의 값을 비교해서 min이 max보다 더 크다면 둘의 자리를 변경해줘야 하기 때문이다

따라서 min은 최소힙으로 max은 최대힙으로 구현한다

출력은 항상 min의 top을 출력하면 된다

 

#include <iostream>
#include <queue>
#pragma warning (disable:4996)
using namespace std;

int main() {
	priority_queue<int, vector<int>> minq;
	priority_queue<int, vector<int>, greater<int>> maxq;
	int n, k;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &k);
		if (i % 2 == 0) minq.push(k);
		else if (i % 2 == 1) maxq.push(k);
		if (!minq.empty() && !maxq.empty()) { // min의 값이 max보다 클 경우 자리 바꿈
			if (minq.top() > maxq.top()) {
				int t = maxq.top();
				maxq.pop();
				maxq.push(minq.top());
				minq.pop();
				minq.push(t);
			}
		}
		printf("%d\n", minq.top());
	}
}