[BOJ 1655, 쉬움] 가운데를 말해요 (C++)

개인적인 난이도

쉬움

 

똥싸면서 생각한대로 구현하니까 풀림

이게 왜 골드 2인지 모르겠다

https://www.acmicpc.net/problem/7662 얘는 비슷한 문제 같은데 아직 못 풀었다 얘는 골드 4임

 

---

실패한 풀이)

set을 이용해서 구현하면 중간값을 쉽게 찾을 수 있다고 생각했다

 

안되는 이유

1. set은 일단 중복된 값을 처리하지 못한다.
2. s.begin()부터 중간값까지 한칸씩 가는 시간이 오래 걸린다. N/2칸 이동을 총 N번 하니까 O(log n^2)임. (이진트리의 이분탐색의 장점을 살리지 못함)

set은 red-black tree. 정렬이 자동으로 되는 균형 잡힌 이진트리임
탐색 시간	O(log n)
삽입/삭제 시간	O(log n)

 

실패 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;

int main(void) {
	fastio;
	set<int> s;
	int N;cin>>N;
	for (int i = 0; i < N; i++)
	{
		int n;cin>>n;
		s.insert(n);
		auto l=s.begin();
		int z = i/2;
		while (z--)l++;
		cout<<*l<<"\n";
	}
	return 0;
}

 

 

---

성공한 풀이)

2개의 priority queue를 이용해서 구현했다, max heap 1개 min heap 1개

 

되는 이유

우선순위 큐는 힙으로 구현되어 있어 삽입 삭제 정렬이 짱빠름. 우선순위 큐의 top 확인은 그냥 O(1)에 가능함

heap은 삽입 삭제 정렬이 빠른 완전 이진 트리임
1번 삽입	O(log n)
1번 삭제	O(log n)
정렬	O(nlog n)

삽입과 삭제 시 이루어지는 heapify 연산의 시간복잡도가 O(log n) 이다.

힙 정렬은 n개 원소를 삽입한 다음 n개 빼내는 방법으로 이루어짐. 그러므로 heapify를 2n번 함.

그러므로 정렬의 시간복잡도는 2n * log n = O(nlog n)

 

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0);
using namespace std;

int main(void) {
	fastio;
	priority_queue<int,vector<int>,greater<int>> pql;
	priority_queue<int,vector<int>> pqg;
	int sg=0,sl=0;
	int N;cin>>N;
	for (int i = 0; i < N; i++)
	{
		int n;cin>>n;
		if(!sg||pqg.top()<n){
			pql.push(n);
			sl++;
		}
		else {
			pqg.push(n);
			sg++;
		}
		if(sl-sg>1){
			pqg.push(pql.top());
			pql.pop();
			sl--;sg++;
		}
		if(sg-sl>1){
			pql.push(pqg.top());
			pqg.pop();
			sg--;sl++;
		}
		if(sg>=sl){
			cout<<pqg.top()<<"\n";
		}
		else cout<<pql.top()<<"\n";
	}
	return 0;
}

min heap을 pql이라고 하고 max heap을 pqg라고 했다(이름을 반대로 지어놨다)

pql.top()에는 가장 작은 값이 저장되어 있고 pqg.top()에는 가장 큰 값이 저장되어 있다. 이 값들이 중간값에 근접하도록 두 우선순위 큐를 유지하면 된다. 그러기 위해서 조건문을 덕지덕지 넣었다

 

여담)

priority_queue의 정렬조건을 less랑 greater로 할 때 뭐가 max heap 이고 뭐가 min heap인지 맨날 헷갈린다

greater가 min heap 이고 less가 max heap임