[백준] 1655 : 가운데를 말해요, 정렬(우선순위 큐)

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

1655번: 가운데를 말해요

 

요즘 백준 문제집에서 단기간 성장이라는 문제집의 문제를 풀고 있다.

(https://www.acmicpc.net/workbook/view/4349)

위 문제는 문제집의 두 번째 문제이다.

 

아주 쉬운 단순 구현 문제인 줄 알았지만, 시간초과가 빡세기 때문에 좀 더 빠른 방법으로 코드를 짜야한다.

위 문제집의 1번 문제도 그렇고, 역시 단기간 성장에는 적당한 난이도의 고난이 필요하다. 😄

 

데이터 정렬

전체 데이터를 한번에 정렬 : std::sort()

특히 vector 자료구조를 사용할 경우 메모리상에서 요소가 연속적으로 배치되므로, 캐시 지역성(빠른 접근)을 활용하여 빠르게 정렬을 수행할 수 있다.

📌 list 자료구조의 경우 메모리가 비연속적이므로, list에서 자체 구현된 sort를 사용하기를 추천한다.

 

sort()의 시간복잡도는 내부 구현이 퀵 정렬로 되어있으므로 O(NlogN)이다.

 

실시간 또는 지속적인 삽입 및 최대/최소 값 접근 : 우선순위 큐

실시간 또는 지속적인 삽입

우선순위 큐에 요소 삽입시 O(logN) - 트리의 높이에 비례 (삽입 연산마다 부모 노드와 비교하여 트리를 내려가며 위치를 조정하기 때문)

📌 우선순위 큐는 힙(heap) 자료구조를 기반으로 한다.

 

최대/최소 값 접근

최대값 : maxHeap에서의 top()

최솟값: minHeap에서의 top()

✅ 우선순위 큐는 가장 앞 원소에만 접근할 수 있다. 중간 값에 바로 접근할 수 없다!

 

중간 값 접근

정렬을 수행하지 않고 빠른 시간 내에 중간 값을 접근하고 싶다면, 중간값을 기준으로 maxHeap과 minHeap으로 요소를 나누어 저장하면 된다.

top()이 중간값을 가리키도록 한다.

중간값 이하 원소 : maxHeap(가장 큰 값이 top)에 저장

=> top() : 중간 값 중 작은값(짝수개) 또는 중간값(홀수개)

 

중간값 초과 원소 : minHeap(가장 작은 값이 top)에 저장

=> top() : 중간값 중 큰 값(짝수개) 또는 중간 값 다음의 값(홀수개)

 

큐 조정작업

그 후 항상 minHeap이 maxHeap보다 크기가 1 크거나(중간값 보유하므로) 같도록 조정하는 작업을 거치면 된다.

조정까지 수행하면 maxHeap의 top이 항상 중간값 중 작은값(짝수개) 또는 중간값(홀수개)이 된다.

간단 로직

 

로직 시간복잡도 : N* logN(원소 삽입) => O(NlogN)

🚨 N개마다 정렬(sort)을 수행했을 경우 N * NlogN => O(N^2 logN) : 처음 시도 방법, 굉장히 느리다..

 

코드

#include <bits/stdc++.h>
using namespace std;
int n, num;
priority_queue<int, vector<int>, greater<int>> minHeap; //오름차순 큐
priority_queue<int> maxHeap; // 내림차순 큐 

int main(){
    cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    // 1. 입력받기
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> num;
        //2. 큐에 원소 삽입하기
        if (maxHeap.empty() || maxHeap.top()>=num){
            maxHeap.push(num);
        }
        else minHeap.push(num);
        //3. 큐 조정작업 수행
        if (maxHeap.size()<minHeap.size()){
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        else if (maxHeap.size()>minHeap.size()+1){
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        //4. 정답 출력
        cout << maxHeap.top() << "\n";
    }
    
}