1655번-가운데를 말해요

참고한 글

---

 

https://www.crocus.co.kr/625

[1655번] 가운데를 말해요

 

중요 지식

---

priority_queue - C++ STL로 우선순위 큐를 간단히 사용할 수 있다.

코드

---

#include <iostream>
#include <queue>

using namespace std;

int main(){
    int N;
    priority_queue<int> maxQ;
    priority_queue<int, vector<int>, greater<int>> minQ;

    cin >> N;

    while(N--){
        int num;

        scanf("%d", &num);

        // 조건 1
        if(maxQ.empty() || maxQ.size() == minQ.size())
            maxQ.push(num);
        else
            minQ.push(num);
        
        // 조건 2
        if((!maxQ.empty() && !minQ.empty()) && maxQ.top() > minQ.top()){
            int a = maxQ.top();
            int b = minQ.top();

            maxQ.pop();
            minQ.pop();

            maxQ.push(b);
            minQ.push(a);
        }

        printf("%d\n", maxQ.top());
    }

    return 0;
}

풀이

---

사전지식

---

두 개의 우선순위 큐(maxQ, minQ)를 만들고 다음 조건을 건다

조건 1. maxQ의 크기는 minQ의 크기와 같거나, 하나 더 크다.
조건 2. maxQ의 최대 원소는 minQ의 최소 원소보다 작거나 같다.

이때 조건 2가 맞지 않다면 maxQ, 최소 힙의 가장 위의 값을 swap해준다.
위 두가지 규칙을 유지해 준다면 항상 maxQ의 top값이 중간값이 된다.

 

알고리즘

---

1-1. 처음 시작할 때 maxQ에 먼저 정수를 push한다 (이유는 maxQ의 top값이 중간값이므로 계속 출력하기 위함)

1-2. maxQ와 minQ의 크기가 같다면, maxQ, 크기가 다르다면 minQ에 push한다.

2. maxQ와 minQ가 비어있지 않고, maxQ.top()값이 minQ.top()값보다 크다면 두 원소를 swap한다

3. 중간값인 maxQ.top()를 출력한다

 

Q&A

---

1. Q : maxQ와 minQ에 값을 번갈아가며 push하는 이유

A : maxQ와 minQ의 의미는 중간을 기준으로 한 왼쪽(작은 값)과 오른쪽(큰 값)이고 top()값의 의미는 중간에 있는 값이란 뜻이다 그래서 왼쪽(작은 값)과 오른쪽(큰 값)의 길이가 같거나 1의 차이가 나야 중간값을 추출할 수 있기 때문에 번갈아가며 넣는 것이다.

 

2. Q : maxQ.top()값이 minQ.top()값보다 크다면 두 원소를 swap하는 이유

A : 일단 maxQ는 왼쪽(작은 값)중 최대값(top)을 추출하고, minQ는 오른쪽(큰 값)중 최소값(top)을 추출한다

만약 maxQ(작은 값)이 minQ(큰 값)보다 크면 안되므로 새롭게 값이 들어올때마다 검사하는 것이다 

 

3. Q : 중간값이 maxQ.top()인 이유

A :  maxQ와 minQ의 길이가 같거나 1의 차이가 나야 중간값을 구할 수 있다 현재 조건에선 maxQ의 길이가 minQ의 길이보다 1만큼 더 클 수 있기 때문에 길이가 더 긴 maxQ의 top()값이 중간값이다  

 

새롭게 알게된 지식

---

priority_queue 

개념 : c++의 STL인 우선순위 큐이다

기능 : 우선순위 큐답게 최소 또는 최대 요소를 빠르게 구할 수 있다 

최대 우선순위 : priority_queue<int, vector<int>, less<int>> (default)

최소 우선순위 : priority_queue<int, vector<int>, greater<int>>

 

자세한 사항은 아래 참고

https://jungeu1509.github.io/algorithm/use-priorityqueue/

C++ STL priority_queue 우선순위 큐 사용법