22.08.04. 풀었던 문제들

LIS 5 문제에 LIS 정리를 해 뒀고
pq 정렬 기준에 대한 정리도 해야 함(pq 첫 문제에 정리 해 둠)

 

22 binary search

12015 LIS 2
12738 LIS 3
14002 LIS 4
14003 LIS 5

 

23 priority queue

11279 최대 힙
1927 최소 힙
11286 절댓값 힙

1655 가운데를 말해요

 상당히 재밌는 문제였다. pq 2개를 써서 가운데 값을 표현할 수 있다.

 [max heap] - middle value - [min heap]으로. 그러나 수가 짝수 개, 홀수 개일 때 middle value를 수정하는 것이 번거롭기 때문에 수가 짝수일 때는 max heap과 min heap의 크기를 동일하게 유지해서 max heap의 top을 middle value로 생각하고, 수가 홀수일 때는 max heap size == min heap size + 1로 유지해서 max heap의 top을 middle value로 일관성 있게 생각할 수 있게 두면 된다.

 input과 middle value를 비교해서 min heap에 넣을지, max heap에 넣을지 결정하고, 항상 [min heap size <= max heap size <= min heap size + 1]이라는 전제를 유지하기 위해 size가 2 이상 차이나면 그것을 없애주는 로직을 넣고, 항상 middle은 max heap top이라는 것을 인지하면 쉽게 풀 수 있다.

int N; cin>>N;

int input; cin>>input;
int mid = input; cout<<mid<<'\n';
priority_queue<int, vector<int>, less<int>> maxh; maxh.push(input);
priority_queue<int, vector<int>, greater<int>> minh;

for(int i = 2; i<=N; i++){
	cin>>input;
	if(input < mid){ // max heap에 값 넣어야 하는 경우
		maxh.push(input);
	}
	else{ // min heap에 값 넣어야 하는 경우
		minh.push(input);
	}

	// size를 맞춰 주어야 함. max heap과 min heap의 차이가 최대 1 나게
	// 같다면 max heap쪽으로 몰아 줌
	if(maxh.size() > minh.size() + 1){
		minh.push(maxh.top());
		maxh.pop();
	}
	if(minh.size() >= maxh.size() + 1){
		maxh.push(minh.top());
		minh.pop();
	}
	mid = maxh.top();
	cout<<mid<<'\n';
}