Algorithm/BOJ
가운데를 말해요 - 1655
jhg0406
2020. 3. 19. 20:29
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
//1655 - 가운데를 말해요
#include <iostream>
#include <queue>
using namespace std;
int N;
priority_queue<int> hq, tq;
void init()
{
hq = tq = priority_queue<int>();
cin >> N;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
init();
int x;
int ht, tt, hsize, tsize;
cin >> x, hq.push(x);
cout << x << "\n";
for(int i = 1; i<N; ++i)
{
cin >> x;
if(hq.size() > tq.size())
{
if(hq.top() <= x)
tq.push(-x);
else
{
tq.push(-hq.top());
hq.pop();
hq.push(x);
}
}
else
{
if(-tq.top() >= x)
hq.push(x);
else
{
hq.push(-tq.top());
tq.pop();
tq.push(-x);
}
}
cout << hq.top() << "\n";
}
}
|
cs |
https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
www.acmicpc.net
가운데를 말해요
우선순위큐를 두개 만들었습니다.
하나는 숫자가 큰것이 우선순위가 높게 설정했고, --> hq
하나는 숫자가 작은것을 우선순위가 높게 설정했습니다. --> tq
hq의 원소의 개수는 tq와 같거나 하나 많은 경우만 가능하고, hq에는 비교적 작은얘들, tq에는 큰 얘들이 들어가게 유지했습니다.
