[백준] 1655번: 가운데를 말해요

 

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

1655번: 가운데를 말해요

---

처음에는 단순하게 생각해서 입력받은 값들을 매번 정렬하여 중간값을 출력했었는데, 그렇게 하니까 시간초과가 났다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	
	int n; cin >> n;
	
	vector<int> v;
	for(int i=0;i<n;i++){
		int k; cin >> k;
		v.push_back(k);
		sort(v.begin(), v.end());
		
		if(i<=1) cout<<v[0];
		else cout<<v[i/2];
	}
	return 0;
}

---

시간초과가 나지 않으려면 우선순위큐를 이용해야 했다

 

우선순위큐(Priority Queue)

•  임의의 순서로 입력된 우선순위가 있는 원소들을 저장하고, 우선순위에 따라 출력하는 자료구조
•  key에 따라 내부 원소들 간의 우선순위를 부여한다

 

---

 

이 문제를 풀기 위해서는 최소힙, 최대힙을 만들고, 아래 규칙에 따라 원소를 정렬하면 된다.

 

1. 최소힙의 크기는 최대힙의 크기보다 커질 수 없다
2. 최대힙의 크기는 최소힙의 크기보다 최대 1만큼 더 크다
3. 최소힙의 값들은 최대힙보다 크다. 
4. 원소 삽입 후, 최대힙의 top이 최소힙의 top보다 크다면 두 값을 swap해준다

 

이렇게 되면 최대힙의 top이 항상 중간값이 된다.

 

---

 

문제에 나온 테스트케이스로 예를 들어 보자!!

입력값: 1, 5, 2, 10, -99, 7, 6

 

1

최대힙 크기가 최소힙 크기보다 커야하므로, 최대힙에 삽입한다

최대힙 [1]  최소힙 [ ]  중간값  1

 

5

최대힙에 삽입하면 최대힙 크기가 최소힙 크기보다 2만큼 커지므로 최대힙에 삽입 불가능

최소힙에 삽입한다

최대힙[1]   최소힙[5]   중간값 1

 

2

최대힙 크기가 최소힙 크기보다 커야하므로, 최대힙에 삽입한다

최대힙[2,1]   최소힙[5]   중간값 2

 

10

최대힙에 삽입하면 최대힙 크기가 최소힙 크기보다 2만큼 커지므로 최대힙에 삽입 불가능

최소힙에 삽입한다

최대힙[2,1]   최소힙[5,10]   중간값 2

 

-99

최대힙 크기가 최소힙 크기보다 커야하므로, 최대힙에 삽입한다

최대힙[2,1,-99]   최소힙[5,10]   중간값 2

 

7

최대힙에 삽입하면 최대힙 크기가 최소힙 크기보다 2만큼 커지므로 최대힙에 삽입 불가능

최소힙에 삽입한다

최대힙[2,1,-99]   최소힙[5,7,10]   중간값 2

 

6

최대힙 크기가 최소힙 크기보다 커야하므로, 최대힙에 삽입한다

최대힙[6,2,1,-99]   최소힙[5,7,10] 

최대힙의 top이 최소힙의 top보다 크므로 두 값을 바꾸어준다!!

최대힙[5,2,1,-99]   최소힙[6,7,10]   중간값 5

---

코드

#include <iostream>
#include <queue>
#include <functional>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
    
	priority_queue<int> max_heap;
	priority_queue<int, vector<int>, greater<int>> min_heap;
	
	int n; cin>>n;
	
	int k;
	for(int i=0;i<n;i++){
		cin >> k;
		 
        //원소 삽입
		if(max_heap.size() == min_heap.size()) max_heap.push(k); 
		else min_heap.push(k);
		
        //최대힙의 top이 최소힙의 top보다 크면 두 값을 바꿔주기
		if(!min_heap.empty() && max_heap.top() > min_heap.top()) {
			int maxtop = max_heap.top();
			int mintop = min_heap.top();
			max_heap.pop(); max_heap.push(mintop);
			min_heap.pop(); min_heap.push(maxtop);	
		}
	
    	//최대힙의 top을 출력
		cout<<max_heap.top()<<"\n";
		
	}
	
	return 0;
}