[BaekJoon 2696번] 중앙값 구하기(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

2696번: 중앙값 구하기

 

 

[문제 설명]

 

 

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

 

 

[입력]

 

 

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.

 

 

[출력]

 

 

각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

 

 

[입출력]

 

 

입력	출력
3 9 1 2 3 4 5 6 7 8 9 9 9 8 7 6 5 4 3 2 1 23 23 41 13 22 -3 24 -31 -11 -8 -7 3 5 103 211 -311 -45 -67 -73 -81 -99 -33 24 56	5 1 2 3 4 5 5 9 8 7 6 5 12 23 23 22 22 13 3 5 5 3 -3 -7 -3

 

 

[문제 풀이]

 

 

홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력해야하는 문제이다.

실시간으로 정렬이 필요하기 떄문에 우선 순위 큐(priority queue)를 사용했다.

 

문제를 풀고 나서 다른 사람들의 풀이를 보았는데, 우선 순위 큐(최대 힙, 최소 힙) 총 2개를 사용했지만

나는 우선 순위 큐(최대 힙) 1개만 사용하여 풀었다.

 

내 알고리즘은 아래와 같다.

 

1. 우선 순위 큐(최대 힙)에  입력받은 수를 넣는다.

 

2. 홀수 번째 수를 입력 받았을 떄  현재까지 입력받은 중앙값을 저장해야하기 때문에

현재 중앙 값이 위치한 인덱스 변수(mididx)를 1 증가 시켜준다.

 

3. 우선 순위 큐의 사이즈가 현재 중앙 값이 위치한 인덱스 변수(mididx)와 같아질 때까지

배열에 우선 순위 큐의 top값을 넣고, 우선 순위 큐에서 값을 빼준다.

 

이렇게 되면 우선 순위 큐(최대 힙)의 top에는 중앙 값만 남게 된다.

 

4. 우선 순위 큐의 top의 값이 있는 배열을 이용하여 다시 우선 순위 큐에 값을 넣으며 복구시켜준다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC; cin >> TC;
    for(int i = 0; i < TC; ++i) {
        int M; cin >> M;
        priority_queue<int> pq;
        vector<int> mid;
        int mididx = 0;
        for(int j = 1; j <= M; ++j) {
            int n; cin >> n;
            pq.push(n);

            if(j % 2 == 0) {
                // 짝수
            } else {
                // 홀수 : 현재 까지 입력의 중앙값을 저장
                mididx += 1;

                vector<int> v;
                while(pq.size() != mididx) {
                    v.emplace_back(pq.top());
                    pq.pop();
                }

                mid.emplace_back(pq.top());

                for(int element : v) {
                    pq.push(element);
                }
            }
        }

        int coutCnt = 0;
        cout << mid.size() << '\n';
        for(int element : mid) {
            coutCnt += 1;
            cout << element << ' ';
            if(coutCnt % 10 == 0) cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}