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

1655 가운데를 말해요

문제

---

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

---

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

---

풀이)

값이 10만개나 들어올 수 있기에, 일일히 값 들어올때마다 sort해서 중간값 찾으면 시간초과가 나는 문제이다.

도저히 생각이 나지 않아 다른 분의 풀이를 보고 도움을 얻었다.

도움받은 곳) https://regularmember.tistory.com/142

heap을 이용해서 푸는 문제인데, 단순히 heap을 구현 & data insert해서 푸는 게 아니였다.

최소값 최대값 찾는 문제가 아니라 중간값을 찾는 문제이다 보니

부모가 항상 자식값보다 큰 값이 저장되는 maxheap과 

부모가 항상 자식값보다 작은 값이 저장되는 minheap 둘 다 이용해서 규칙을 찾는 문제였다.

(heap은 priority_queue로 구현)

두 개의 힙을 이용하면서 만족해야하는 조건은 아래와 같았다.

1. minheap 의 값들은 모두 maxheap의 값보다 크다. 즉, maxheap의 top은 minheap의 top보다 작거나 같다.

2. maxheap 의 크기는 minheap의 크기와 같거나, 1 더 크다.

=> 먼저 크기만 고려해서 heap에 값을 넣은 후

maxheap 과 minheap의 top 값을 비교해서 minheap 의 top보다 maxheap의 top이 더 크다면 두 값을 교환해준다.

각 경우마다 maxheap 의 top값이 중간값이 된다.

문제 입력 예시)

1 5 2 10 -99 7 5

minheap    maxheap
[]             [1]                maxheap이랑 minheap이랑 size가 같으므로 maxheap에 1삽입     중간값: 1
[5]            [1]                maxheap이 minheap보다 1크므로 minheap에 5삽입                  중간값: 1
[5]            [2 1]             maxheap이랑 minheap이랑 size가 같으므로 maxheap에 2삽입     중간값: 2
[10 5]        [2 1]             maxheap이 minheap보다 1크므로 minheap에 10삽입                 중간값: 2

[10 5]        [2 1 -99]                                                                                             중간값: 2

[10 7 5]     [2 1 -99]                                                                                             중간값: 2

[10 7 5]     [5 2 1 -99]                                                                                          중간값: 5

+ 참고사항

c++에서 priority_queue는 기본적으로 내림차순 정렬이기 때문에  

부모값이 더 커야하는 maxheap은 그냥 우선순위 큐로 하나 만들어주면 되고,

부모값이 더 작아야하는 minheap은 greater<int>를 이용해서 priority_queue의 성질을 오름차순 정렬로 바꿔줘야한다.

(greater은 <functional> 헤더를 include해줘야 사용 가능)

코드)

#include <stdio.h>
#include <queue>
#include <functional> //greater<int>사용하기 위해
using namespace std;
 
int N, temp;
 
int main() {
    scanf("%d", &N);
    
    priority_queue <int> maxheap;
    priority_queue<int, vector<int>, greater<int>> minheap;
    for (int i = 1; i <= N; i++) {
        scanf("%d", &temp);
        if (maxheap.size() == 0) maxheap.push(temp);
        else {
            if (maxheap.size() > minheap.size()) minheap.push(temp);
            else maxheap.push(temp);
 
            if (maxheap.top() > minheap.top()) {
                int num1 = maxheap.top();
                int num2 = minheap.top();
                maxheap.pop();
                minheap.pop();
                maxheap.push(num2);
                minheap.push(num1);
            }
        }
        printf("%d\n", maxheap.top());
    }
    
    return 0;
}