[백준][C++/Python] 1655번: 가운데를 말해요 (251)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

생각의 흐름

사실 다행이도 문제를 보자마다 Heap이 가장 먼저 떠올랐다.

각각 최소힙과, 최대힙 을 사용하여 잘 처리하면 될것같은데? 라는 생각을 하였다.

 

우선 짝수, 홀수 순서로 나누어 삽입연산을 진행한다.

 

숫자를 입력으로 받으면서, 처음부터  중간값 까지를 최대 힙에 저장하려고 노력할 것 이다.

이럴 경우 최대 힙의 top이 정답인, 중간 값이 된다.

 

중간값 이후부터 끝 값까지는 최소 힙에 저장하자.

만약 새로운 수가 최소 힙의 top보다 크다면 최소 힙 쪽에 포함되어야 한다.

하지만 이런 경우 최소 힙 쪽이 중간값부터 끝 값까지의 범위를 저장하게 된다. (즉, 최소힙 쪽이 원소의 수가 더 많아진다)

따라서 최소 힙의 top을  최대 힙으로 넘겨주어야 서로의 크기가 같아지도록 만든다.

 

또 주의할점이 Python의 heapq는 기본적으로 min_heap만 지원한다.

따라서 max_heap을 만들려면 값을 추가할 때 -1을 곱해주고, 값을 반환받을때 다시 -1을 곱해주는 방식을 취해야 한다.

(C++ 만세!!)

 

나의 코드

1) C++ 코드

#include <bits/stdc++.h>
using namespace std;

int N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int>> min_pq;

    max_pq.push(-10001);
    min_pq.push(10001);

    cin >> N;
    for(int i = 1; i <= N; i++) {
        int num;
        cin >> num;

        if(i % 2 == 1) {
            if(num < min_pq.top()) {
                max_pq.push(num);
            } else {
                int top = min_pq.top();
                min_pq.pop();
                max_pq.push(top);
                min_pq.push(num);
            }
        } else {
            if(num > max_pq.top()) {
                min_pq.push(num);
            } else {
                int top = max_pq.top();
                max_pq.pop();
                min_pq.push(top);
                max_pq.push(num);
            }
        }
        cout << max_pq.top() << "\n";
    }

    return 0;
}

 

2) Python 코드

C++과 달리 max_pq, min_pq 를 모두 10001로 초기화 했는데, 이는 파이썬에서는 최대힙을 구현하려면 -1을 곱해서 삽입해줘야 하는 방식 때문입니다...

import sys
import heapq

N = int(sys.stdin.readline())
max_pq = [10001]
min_pq = [10001]

for i in range(1, N + 1):
    inputNum = int(sys.stdin.readline())
    if i % 2 == 1:
        if inputNum < min_pq[0]:
            heapq.heappush(max_pq, -inputNum)
        else:
            temp = heapq.heappop(min_pq)
            heapq.heappush(max_pq, -temp)
            heapq.heappush(min_pq, inputNum)
    else:
        if inputNum > -max_pq[0]:
            heapq.heappush(min_pq, inputNum)
        else:
            temp = -heapq.heappop(max_pq)
            heapq.heappush(min_pq, temp)
            heapq.heappush(max_pq, -inputNum)
    print(-max_pq[0])