백준 1655 가운데를 말해요
알고리즘
1) Max Heap 과 Min Heap 두개를 생성
전체 숫자가 정렬된 벡터가 있다고 했을때 이때, 첫번째 값부터 ~ 중간값의 값은 오름차순이고 이부분은 MaxHeap으로 두고 중간값 이후 부터 벡터의 끝 부분도 오름차순이고 가장 작은 값이 필요하기에 MinHeap으로 설정한다!Maxheap는 Minheap의 size보다 같거나 1개 커야 한다
ex) 1 2 3 4 5 ( 123 이 maxheap, 45 minheap )2) Maxheap 의 top 값은 Minheap의 top 값보다 작아야 한다! 이를 위배한다면 두 값을 Swap
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
public class test {
static int N;
static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
static PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
for(int i=1; i<= N; i++) {
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
int minSize = minHeap.size();
int maxSize = maxHeap.size();
if(minSize == maxSize) maxHeap.add(-num);
else minHeap.add(num);
minSize = minHeap.size();
maxSize = maxHeap.size();
if(minSize == 0) {
bw.write(-maxHeap.peek()+"\n");
continue;
}
int maxNum = -maxHeap.peek();
int minNum = minHeap.peek();
if(maxNum > minNum) {
maxHeap.poll();
minHeap.poll();
maxHeap.add(-minNum);
minHeap.add(maxNum);
}
bw.write(-maxHeap.peek()+"\n");
}
bw.flush();
}
}