[C++] 중앙값 제거 (백준 23758번)

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

 

#include <iostream>
#include <queue>
using namespace std;

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

    int n;
    cin >> n;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    int tmp = n / 2;
    while (tmp--) pq.pop();

    int cnt = 0;
    while (1) {
        int cur = pq.top();
        pq.pop();
        int nxt = cur / 2;
        cnt++;
        if (nxt == 0) {
            cout << cnt << '\n';
            break;
        }
        pq.push(nxt);
    }
}

생각해보면 중간값을 기준으로 더 큰 값들은 절대 더 작아질 수 없고 변화없이 중간값보다 큰쪽에 유지된다. 즉, 변화하는 값들은 중간값보다 작거나 같은 값들이므로 걔네들만 배열에 넣어서 체크해주면 된다. 그 배열에서의 최댓값이 중간값인 셈이므로 우선순위큐로 그 값들을 관리하면 된다. 최댓값을 뽑고 2로 나눈값을 다시 넣고... 이렇게 반복하도록 코드를 짰다.

그런데 이렇게 제출하면 시간 초과를 받게 된다. (TLE)

 

좀더 생각해보면, 0이 등장할 수 있다는 건 그 때 중간값이 1이라는 의미이다. 그리고 0이 처음으로 등장한다는 건 아직 0이 존재하지 않는다는 뜻이고, 그건 다시 말해 1인 중간값보다 작거나 같은 값들이 모두 1이라는 의미이기도 하다. 따라서 중간값보다 작거나 같은 값들에 대해 얼마나 나눠야 2보다 작거나 같아지는지를 구해 모두 더해서 그 값에 1만 더해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    int cnt = 0;
    int tmp = (n + 1) / 2;

    for (int i = 0; i < tmp; i++) cnt += log2(a[i]);

    cout << cnt + 1 << '\n';
}

(AC)