[Baekjoon Online Judge] 백준 1655번 가운데를 말해요(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

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

(C++, Python)

(글쓴날 : 2020.04.27)

 

---

* Baekjoon Online Judge, 백준 1655번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1655번 가운데를 말해요

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

N개의 정수가 주어질 때마다 현재까지 주어진 정수 중에서 중간값을 구하는 문제입니다.

단, 정수의 개수가 짝수일 경우 가운데의 두 수 중 작은 수를 출력합니다.

 

저의 경우, 우선순위 큐를 적용하였으며, C++과 Python을 사용했습니다.

문제에서 주어지는 N이 최대 100000이므로 만약, 총 시간 복잡도가 O(n²)이 되는 로직을 구현 시 시간 초과가 발생하게 됩니다.

따라서, 중간값을 O(log n)에 찾기 위해 우선순위 큐를 적용했고,

내부를 각각 Min Heap과 Max Heap으로 구현한 우선순위 큐 두 개를 생성하여, 중간 값을 기준으로 작은 값들을 Max Heap 기반 우선순위 큐에, 큰 값들을 Min Heap 기반 우선순위 큐에 저장하고 동시에 중간 값을 계속 갱신하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
#include <cstdlib>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    int middleValue = 0;
    priority_queue<int> smallPQ;
    int smallPQCount = 0;
    priority_queue<int, vector<int>, greater<int>> bigPQ;
    int bigPQCount = 0;
 
    int tempValue = 0;
    int inputValue = 0;
 
    for (int i = 0; i < N; i++)
    {
        cin >> inputValue;
 
        if (!i)
        {
            middleValue = inputValue;
            cout << middleValue << "\n";
            continue;
        }
 
        if (inputValue >= middleValue)
        {
            smallPQ.push(middleValue);
            smallPQCount++;
 
            if (!abs(smallPQCount - bigPQCount))
            {
                bigPQ.push(inputValue);
                middleValue = bigPQ.top();
                bigPQ.pop();
                cout << middleValue << "\n";
            }
            else if (abs(smallPQCount - bigPQCount) == 2)
            {
                tempValue = smallPQ.top();
                smallPQ.pop();
                smallPQCount--;
                bigPQ.push(inputValue);
                bigPQCount += 1;
                bigPQ.push(tempValue);
                middleValue = bigPQ.top();
                bigPQ.pop();
                cout << middleValue << "\n";
            }
            else
            {
                cout << middleValue << "\n";
                bigPQ.push(inputValue);
                middleValue = bigPQ.top();
                bigPQ.pop();
            }
        }
        else
        {
            bigPQ.push(middleValue);
            bigPQCount++;
 
            if (!abs(smallPQCount - bigPQCount))
            {
                smallPQ.push(inputValue);
                middleValue = smallPQ.top();
                smallPQ.pop();
                cout << middleValue << "\n";
            }
            else if (abs(smallPQCount - bigPQCount) == 2)
            {
                tempValue = bigPQ.top();
                bigPQ.pop();
                bigPQCount--;
                smallPQ.push(inputValue);
                smallPQCount += 1;
                smallPQ.push(tempValue);
                middleValue = smallPQ.top();
                smallPQ.pop();
                cout << middleValue << "\n";
            }
            else
            {
                smallPQ.push(inputValue);
                middleValue = smallPQ.top();
                smallPQ.pop();
                cout << middleValue << "\n";
            }
        }
    }
 
    return 0;
}

---

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
N = int(input())
middleValue = 0
smallHQ = []
smallHQCount = 0
bigHQ = []
bigHQCount = 0
 
for i in range(N):
    inputValue = int(input())
 
    if not i:
        middleValue = inputValue
        print(middleValue)
        continue
    
    if inputValue >= middleValue:
        heapq.heappush(smallHQ, (-middleValue, middleValue))
        smallHQCount += 1
 
        if not abs(smallHQCount - bigHQCount):
            heapq.heappush(bigHQ, (inputValue, -inputValue))
            middleValue = -heapq.heappop(bigHQ)[1]
            print(middleValue)
        elif abs(smallHQCount - bigHQCount) == 2:
            tempValue = heapq.heappop(smallHQ)[1]
            smallHQCount -= 1
            heapq.heappush(bigHQ, (inputValue, -inputValue))
            bigHQCount += 1
            heapq.heappush(bigHQ, (tempValue, -tempValue))
            middleValue = -heapq.heappop(bigHQ)[1]
            print(middleValue)
        else:
            print(middleValue)
            heapq.heappush(bigHQ, (inputValue, -inputValue))
            middleValue = -heapq.heappop(bigHQ)[1]
    else:
        heapq.heappush(bigHQ, (middleValue, -middleValue))
        bigHQCount += 1
 
        if not abs(smallHQCount - bigHQCount):
            heapq.heappush(smallHQ, (-inputValue, inputValue))
            middleValue = heapq.heappop(smallHQ)[1]
            print(middleValue)
        elif abs(smallHQCount - bigHQCount) == 2:
            tempValue = -heapq.heappop(bigHQ)[1]
            bigHQCount -= 1
            heapq.heappush(smallHQ, (-inputValue, inputValue))
            smallHQCount += 1
            heapq.heappush(smallHQ, (-tempValue, tempValue))
            middleValue = heapq.heappop(smallHQ)[1]
            print(middleValue)
        else:
            heapq.heappush(smallHQ, (-inputValue, inputValue))
            middleValue = heapq.heappop(smallHQ)[1]
            print(middleValue)

---