BOJ 1655 - 가운데를 말해봐 문제풀이

문제를 읽고 이해하기

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

 

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

 

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

재정의와 추상화

최대 힙, 최소 힙을 이용해 중간값을 구하는 알고리즘을 이용해야 한다. 필자는 이 문제를 접하기 전에는 그 알고리즘에 대해 몰랐으므로 아래와 같은 방법을 시도했었다.

 

시도 1

vector에 값을 받을 때마다 정렬하고 중간값 인덱스로 접근하여 출력
인덱스 접근은 O(1)이나, 값을 받을 때마다 정렬하므로 매번 O(n * logn) (sort 함수의 시간복잡도) 만큼의 시간이 발생한다. 따라서 최대 길이인 100,000이 N일 경우, O(1 * log1) + O(2 * log2) + ... + O(100,000 * log(100,000))이므로 계산해보면 10억이 넘으므로, 시간초과가 발생한다.

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

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    vector<int> v;

    cin >> n;

    while (n--) {
        int temp;
        cin >> temp;
        v.push_back(temp);
        sort(v.begin(), v.end());

        if (v.size() % 2 == 0)
            cout << v[v.size() / 2 - 1] << '\n';
        else
            cout << v[v.size() / 2] << '\n';
    }
    return 0;
}

 

시도 2

2개의 priority_queue를 선언하고 pq에 값을 추가하고, 똑같은 값들을 가진 temp_pq를 pq에 대한 복사생성하고, pq.size() / 2만큼 temp_pq를 pop한 후, temp_pq의 최상단 값을 불러온다. 이 시도 또한 복사생성에 O(n), pop()에 O(n / 2)만큼의 시간이 걸리므로 시간 초과가 발생한다.

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

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    priority_queue<int> pq;

    cin >> n;

    while (n--) {
        int temp;
        cin >> temp;
        pq.push(temp);
        priority_queue<int> temp_pq(pq);

        for (int i = 0; i < pq.size() / 2; i++)
            temp_pq.pop();

        cout << temp_pq.top() << '\n';
    }
    return 0;
}

 

결국, 구글신께 여쭤봤다... (구글신은 모든 것을 알고 있기에..)

 

이 문제를 풀기 위해서는 최대 힙과 최소 힙을 이용해 중간값을 구하는 알고리즘을 알아야 한다는 것이다. 그 알고리즘은 아래와 같다.

 

1) 최대 힙, 최소 힙을 담당하는 우선순위 큐(priority_queue) 변수 2개를 선언한다.

priority_queue<int, vector<int>, less<>> max_heap;
priority_queue<int, vector<int>, greater<>> min_heap;

2) 아래 규칙을 따라 최대 힙과 최소 힙에 push/pop을 진행한다.

1. 최대 힙 변수의 원소 개수는 최소 힙 변수의 원소 개수보다 1개 더 많거나 같아야 한다.
2. 최대 힙 변수의 최상단 값(최댓값)은 최소 힙 변수의 최상단 값(최소값)보다 작거나 같아야 한다.

 

코드 작성

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

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    priority_queue<int, vector<int>, less<>> max_heap;
    priority_queue<int, vector<int>, greater<>> min_heap;

    cin >> n;

    while (n--) {
        int temp;
        cin >> temp;
        if (max_heap.size() - min_heap.size() == 0)
            max_heap.push(temp);
        else
            min_heap.push(temp);

        if (!max_heap.empty() && !min_heap.empty()) {
            if (max_heap.top() > min_heap.top()) {
                max_heap.push(min_heap.top());
                min_heap.pop();
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
        }
        cout << max_heap.top() << '\n';
    }
    return 0;
}