1655번 가운데를 말해요(우선순위 큐) - ☆
#문제링크 : www.acmicpc.net/problem/1655
<전략>
1. 힙 배열을 둘로 나누어 관리한다. 앞배열과 뒷배열로 나눈다.
2. 모든 앞배열의 수는 모든 뒷배열의 수보다 작다. 단, 앞배열의 최댓값과 뒷배열의 최솟값은 같을 수 있다.
3. 전체 수열에서 중간값으로 될 수 있는 후보는, 앞배열의 최댓값 or 뒷배열의 최솟값이다.
4. 앞배열에서는 최댓값을 살펴봐야하므로 앞배열은 최대 힙으로 구성한다.
5. 뒷배열에서는 최솟값을 살펴봐야하므로 뒷배열은 최소 힙으로 구성한다.
6. 입력을 받고, 앞배열과 뒷배열에 저장할때, 앞배열과 뒷배열의 크기가 비슷해야한다. 더 정확하게 말하면 앞배열의 크기가 뒷배열의 크기와 같거나 뒷배열보다 하나 더 커야한다. (반대로, 뒷배열을 하나 더 크게 구현해도 상관없다.)
7. 입력값이 들어왔을때, 앞배열의 크기 > 뒷배열의 크기 면, 지금은 뒷배열에 넣을 차례인 것이다.(크기를 비슷하게 맞춰야 하므로) 근데, 입력 받은 숫자가 앞배열의 최대값보다 작다면, 이 숫자는 앞배열로 들어가야만 한다. 그래서, 우선 앞배열로 넣고, 대신 앞배열에서 제일 큰 값을 빼내어 뒷배열로 넣어준다. 반대로, 입력 받은 숫자가 앞배열의 최대값보다 같거나 크다면 그냥 뒷배열로 넣어준다.
8. 입력값이 들어왔을때, 앞배열의 크기 <= 뒷배열의 크기 면, 지금은 앞배열에 넣을 차례인 것이다. 근데, 입력받은 숫자가 뒷배열의 최소값보다 크다면, 이 숫자는 뒷배열로 들어가야만 한다. 그래서, 우선 뒷배열에 넣고, 대신 뒷배열에서 제일 작은 숫자를 빼내어 앞배열로 넣어준다. 반대로, 입력 받은 숫자가 뒷배열의 최소값보다 작거나 같다면 그냥 앞배열로 넣어준다.
9. 이제껏 입력으로 들어왔던 숫자의 갯수가 홀수면, 앞배열의 제일 큰값을 출력하고, 짝수면, 앞배열의 최대값과 뒷배열의 최소값 중에 작은 녀석으로 출력한다.
