1655

백준 1655 풀이 (가운데를 말해요, 우선순위 큐)

이 문제는 우선순위 큐를 이용하여 중간에 존재하는 값을 출력하면 된다. 방법은 우선순위 큐를 2개 만들어서 푸는 문제이다. 최대 힙과 최소 힙을 사용하여 정렬을 유지하면 된다. 왜 이런 방식을 사용해야 하냐 만약 우선순위 큐에 값을 넣으면 저렇게 배열이 된다. 그래서 저 상태로는 중간값을 뽑을 수가 없다. 그런데 최대힙과 최소힙을 사용하면 중간값을 찾을 수 있다. 우선 최대힙의 [0]위치에는 최댓값 4를 가지고 최소힙의 [0]위치에는 최솟값 7을 가진다. 따라서 모든 힙이 정렬되지 않아도 중간값이 4라는 것을 알 수 있다. 따라서 새로운 입력에 대해서 최대힙의 개수와 최소힙의 개수를 동일한 비율로 맞춰주면 문제가 없다. 그러나 새롭게 입력되는 값이 -99인경우 최소힙에 3개의 값이 들어있기 때문에 -99..