백준 g2 1655 가운데를 말해요 c++ (set, priority queue)

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

1655번: 가운데를 말해요

 

문제

백준이가 N개의 숫자를 말한다.

백준이의 동생은 지금까지 나온 N개의 숫자 중 중간값을 말해야 한다. 만약 개수가 짝수일 경우에는 더 작은 수를 말한다.

 

N <= 10^5, 제한 시간 0.5초

 

풀이1. set을 이용한 풀이

우선순위큐 단원이지만 set으로 풀릴 거 같아서 해봤더니 풀림

 

중간값을 cursor로 두고, 이 커서의 양 옆에 숫자가 추가됨에 따라 커서가 한 칸씩 움직이는 점을 착안해서 O(NlgN)에 풀었다. O(N번 숫자 말하기 * set에 숫자 삽입 lgN)

 

set의 원래 개수가 짝수or홀수냐, 그리고 새로운 값이 왼쪽or 오른쪽에 추가됨에 따라 4가지 경우의 수가 있다.

 

1. 원래 개수가 짝수고, 새로운 값이 왼쪽에 추가 되는 경우 ex. 1 2 5 10 -> -99 1 2 5 19
   
   • 그대로
2. 원래 개수가 짝수고, 새로운 값이 오른쪽에 추가 되는 경우 ex. 1 2 5 10 -> 1 2 2 5 10
   
   • cursor++
3. 원래 개수가 홀수고, 새로운 값이 왼쪽에 추가 되는 경우 ex. 1 2 5 -> -99 1 2 5
   • cursor--
4. 원래 개수가 홀수고, 새로운 값이 오른쪽에 추가 되는 경우 ex. 1 2 5 -> 1 2 5 10
   • 그대로

전체 코드

/*boj g2 1655 가운데를 말해요*/
#include <iostream>
#include <set>
#define MAXN 105
using namespace std;

int N;
multiset<int> s;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    // 1. 맨 처음
    N--;
    int x;
    cin >> x;
    s.insert(x);
    auto cur = s.begin();
    cout << *cur << "\n";

    // 2. 그 다음
    while (N--) {
        cin >> x;
        s.insert(x);

        if (s.size() % 2 == 1 && x < *(cur)) {
            cout << *cur << "\n";
        } else if (s.size() % 2 == 1 && x >= *(cur)) {
            cur++;
            cout << *cur << "\n";
        } else if (s.size() % 2 == 0 && x < *(cur)) {
            cur--;
            cout << *cur << "\n";
        } else if (s.size() % 2 == 0 && x >= *(cur)) {
            cout << *cur << "\n";
        }
    }
}

 

 

풀이 2. priority queue를 이용한 풀이

set은 느린 lgN(내부 동작이 많음), pq는 그냥 lgN이라 확실히 메모리, 시간이 2배 이상 차이가 난다.

 

위 풀이와 마찬가지로 균형을 맞추는 게 중요하다. 

1. mid값 보다 작은 값을 담는 maxHeap

2. mid값 보다 크거나 같은 값을 담는 minHeap

3. mid값

 

이렇게 셋이서 수를 나눠 먹는다.

 

만약 개수가 2개 이상 차이나면, 중간값에 변동이 있다는 뜻이므로

ex. | 1 |     2     | 5, 10 | -> | 1 |    2    |5, 10, 15|

 

원래의 mid를 개수가 더 적은 heap에 넣고, mid는 개수가 많은 heap.top()을 가져온 후 heap.pop()을 하면 균형이 유지된다.

 

이때 주의할 점은, 개수가 짝수인 경우에는 작은 수를 택하므로, 

ex. | 1 , 1 |   2   | 5 | 

다음과 같은 경우에는 개수가 1만 차이나도 중간값을 바꿔주는 작업을 해야 한다.

 

수도 코드

//1. insert
if x < mid smaller.push(x)
else bigger.push(x)
    // 값이 크거나 같을 때도, 1 2 2 5의 경우에 앞의 2를 택하므로 bigger heap에 넣어주어야 한다

//2. 검사
if smaller의 크기 - bigger의 크기가 1 이나 2면
    bigger.push(mid)로 균형 맞춰주고
    mid = smaller.top
    smaller.pop()
else
    반대로
    
//3. 출력
cout << mid << "\n";

 

 

전체 코드

/*boj g2 1655 가운데를 말해요_priority queue*/
#include <iostream>
#include <queue>
#define MAXN 105
using namespace std;

int N;
priority_queue<int> smaller;                           // mid보다 작은 수를 넣을 maxHeap
priority_queue<int, vector<int>, greater<int>> bigger; // mid보다 큰 수를 넣을 minHeap
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    // 1. 맨 처음
    N--;
    int x;
    cin >> x;
    int mid = x;
    cout << mid << "\n";

    // 2. 그 다음
    while (N--) {
        // 1. insert
        cin >> x;
        if (x < mid)
            smaller.push(x);
        else
            bigger.push(x);

        // 2. 검사
        if (smaller.size() - bigger.size() == 2 || smaller.size() - bigger.size() == 1) {
            bigger.push(mid);
            mid = smaller.top();
            smaller.pop();
        } else if (bigger.size() - smaller.size() == 2) {
            smaller.push(mid);
            mid = bigger.top();
            bigger.pop();
        }

        // 3. 출력
        cout << mid << "\n";
    }
}