[SWEA] 3000. 중간값 구하기

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-fO0s6ARoDFAXT

SW Expert Academy

풀이 과정

• MIN HEAP과 MAX HEAP을 각각 두어서 MAX HEAP의 TOP이 항상 MIN HEAP의 top에 있는 값보다 작은 값이 되도록 유지시키면 MAX HEAP의 top이 중간값이 될 것이다.
• 다음은 문제에 나온 예시를 시각화한 것이다.

5로 시작 1, 3 삽입

2, 6 삽입

8, 9 삽입

• MAX HEAP의 top (초록색)은 항상 중간값을 나타낸다.
• priority queue를 이용해서 MAX Heap과 MIN Heap 구현
• N개의 중간값들을 매번 출력하면 출력양이 너무 많기 때문에, 그 수들의 합을 20171109로 나눈 나머지를 출력하는 프로그램을 작성하시오.
  • 계속 더하고 나중에 20171109로 나눠버리면 틀림 -> 최대 크기를 넘어버리기 때문에 오버플로우가 발생해서 제대로 된 값이 나오지 않음 -> Modulo 연산의 분배법칙 이용

// 모듈로 연산의 분배법칙
(A + B) % p = ((A % p) + (B % p)) % p // 이걸 이용!
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p
(A / B) % p = (A * B^(p-2)) % p = ((A % p) * (B^(p-2) % p)) % p

풀이 코드

 

#include<iostream>
#include<queue>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	int N;
    int X;
    int Y;
    int result;
    cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        priority_queue<int> max_pq;
        priority_queue<int, vector<int>, greater<int> > min_pq;
        cin >> N >> X;
        max_pq.push(X);
        result = 0;
        for(int i = 0; i < N; i++){
            cin >> X >> Y;
            min_pq.push(X);
            max_pq.push(Y);

            if(max_pq.top() > min_pq.top()){
                int temp = max_pq.top();
                max_pq.pop();
                max_pq.push(min_pq.top());
                min_pq.pop();
                min_pq.push(temp);
            }

            result = (result + max_pq.top()) % 20171109;
        }
        cout << "#" << test_case << " " << result<< '\n';
	
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}