[Week 3] RUNNINGMEDIAN self review - Yunhyunjo

[Yunhyunjo]

RUNNINGMEDIAN self review

• 파일명: PQR/RUNNINGMEDIAN/Yunhyunjo.cpp
• 수행시간: 16ms

1. 고민 과정

어떻게 비교하여 현재 값을 넣어줘야 할 지를 고민하였습니다.
처음에는 현재 값과 최대 힙의 최대값을 비교해 주었는데 값이 나오지 않았고, 값이 아닌 크기를 비교하는 방식으로 다시 코드를 작성하였습니다.

2. 풀이 아이디어

맨 처음 값은 고정이므로 먼저 최대힙에 넣어줬습니다.
그 다음 for 문을 돌면서 현재 값을 구해주고, 최대힙과 최소힙의 크기를 비교하여 같다면 최대힙, 아니라면 최소힙에 넣어주었습니다. 그 다음 최소힙과 최대힙의 값을 비교하여 최대힙의 값이 최소힙의 값보다 크다면 서로의 root를 변경해주었습니다.
마지막으로 홀수개라면 앞에 함수들로 인해 무조건 최대힙이 한 개가 더 많을 것이고 짝수개라면 작은 값을 선택하라 했으니 최대힙의 값을 sum 에 더해주었습니다.

3. 작성한 코드와 설명

priority_queue <int, vector <int>, greater<int>> low;
priority_queue <int> high;
p = 1983;
sum = 1983;
high.push(p);
for (int i = 1; i < n; i++) {
	now = ((p * a) + b) % 20090711;
	if (high.size() == low.size()) high.push(now);
	else low.push(now);
	if (high.top() > low.top()) {
		tmp = high.top();
		high.pop();
		high.push(low.top());
		low.pop();
		low.push(tmp);
	}
	sum += (high.top() % 20090711);
	p = now;
	sum %= 20090711;
}

첫 번째 값은 모두 동일하기 때문에 미리 세팅을 해 두고 for문을 1부터 돌았습니다.
우선순위 큐의 사이즈를 비교하여 어디에 값을 넣을 지를 정했고, 각각 root값을 비교하여 정리해 주었습니다.
정리를 하고 나면 중간값은 최대힙의 값이므로 sum에 최대힙의 값을 더해주었습니다.