백준 1655 가운데를 말해요(Gold 2, Python, C++)

in Algorithm on Python, C++, Baekjoon, Priorityqueue, Heapqueue
백준 1655 가운데를 말해요(Gold 2, Python, C++)

가운데요 말해요 문제를 풀어봅시다!

가운데를 말해요

문제 설명

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

예를 들어 백준이가 동생에게 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줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

예제 입력

7 1 5 2 10 -99 7 5

예제 출력

1 1 2 2 2 2 5

정답

C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    priority_queue<int> max_pq, min_pq;
    int n;
    cin >> n;
    while (n--){
        int a;
        cin >> a;
        if(min_pq.size() > max_pq.size())   max_pq.push(-a);
        else                                min_pq.push(a);

        if(!min_pq.empty() && !max_pq.empty() && min_pq.top() > -max_pq.top()){
            int tmp_min_pq_top = min_pq.top();
            min_pq.pop();
            int tmp_max_pq_top = -max_pq.top();
            max_pq.pop();

            min_pq.push(tmp_max_pq_top);
            max_pq.push(-tmp_min_pq_top);
        }
        cout << min_pq.top() << "\n";
    }

    return 0;
}

Python

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
min_hq, max_hq = [], []
while n:
    a = int(sys.stdin.readline().rstrip())
    if len(min_hq) > len(max_hq):
        heapq.heappush(max_hq, a)
    else:
        heapq.heappush(min_hq, -a)
    if min_hq and max_hq and -min_hq[0] > max_hq[0]:
        min_val, max_val = -heapq.heappop(min_hq), heapq.heappop(max_hq)
        heapq.heappush(min_hq, -max_val)
        heapq.heappush(max_hq, min_val)
    print(-min_hq[0])
    n -= 1

풀이

이 문제를 처음 봤을 때(알고리즘 1도 모를 때), 그냥 max, min연산을 계속 취하면서 하면 되는거 아닌가…? 라는 정말 무식한 생각을 했었습니다.

하지만 문제의 의도는 이게 아니죠. 시간 복잡도도 정말 절망적으로 나올거구요

그럼 어떻게 해결해야 할까요??

바로 우선순위 큐를 2개 사용하면 됩니다. (오름차순, 내림차순 각 1개 씩) 그럼 어떻게 사용하면 될까요??

바로 큐가 서로 마주보게(??) 하면 됩니다!! 이게 무슨 소리냐고요?? 그림으로 한 번 보겠습니다.

위의 그림과 같이 두 우선순위 큐의 Head가 서로 마주보도록 설계하면 됩니다.

왜 이렇게 할까요? 바로 정 가운데를 말하기 위해서는 두 우선순위 큐의 가장 위에 있는 값을 알아야 하기 때문입니다.

로직을 설명하자면 다음과 같습니다.

  1. 최대힙과 최소힙 2개를 선언한다.
  2. 값 a를 받는다.
    1. 만약 최대힙의 크기가 최소힙의 크기가 같다
      1. 최대 힙에 a를 삽입한다.
    2. 최대힙의 크기가 최소힙의 크기보다 크다
      1. 최소 힙에 a를 삽입한다.
  3. 최소힙의 head와 최대 heap의 크기를 비교한다.
    1. 만약 최대힙의 head 의 값이 최소힙의 head 보다 크다
      1. 서로의 head에 위치한 값을 교환한다.
  4. 최대 힙의 head가 가운데에 위치한 값이다. 끝!

문제에서 숫자를 하나씩 줄 때마다 해당 숫자를 받고, 받은 모든 숫자들을 정렬했다고 했을때 절반으로 나누고, 작은 절반은 최대 힙, 큰 절반은 최소 힙에 들어가 있다고 생각하면 됩니다.

감사합니다.