[G2] 백준 2696번 중앙값 구하기 C++ 우선순위 큐

리뷰

 

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

최소/최대 힙을 사용해 풀이한 문제, 별개로 출력 기준이 좀 까다롭다.

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• m : 테스트 케이스당 수열의 크기를 저장할 변수

 

함수

없음

 

 

문제풀이

1. t값을 입력 받고, t번의 테스트케이스를 수행해준다.
2. 매 테스트케이스마다 변수 m을 입력 받고, (m+1)/2를 출력 후 개행문자를 삽입해준다.
3. 최소 힙 asc와 최대 힙 desc를 초기화하고, 변수 outs을 0으로 초기화한다.
4. 변수 i로 1~m을 인덱스로 하는 for문을 개행하고, 매 루프마다 변수 a에 값을 입력받는다.
5. desc가 비었다면 desc에 a를 push한다.
6. asc가 비었다면 asc에 a를 push한다.
7. desc의 top()이 a보다 크다면 desc에 a를 push한다.
8. 위 세 조건에 부합하지 않을 경우 asc에 a를 push한다.
9. desc, asc가 비지 않았고, desc의 top()이 asc의 top()보다 크다면 asc로 desc의 top()요소를 옮긴다.
10. desc의 크기가 asc의 크기보다 2이상 클 경우 asc로 desc의 top()요소를 옮긴다.
11. desc의 크기가 asc크기보다 작을 경우 desc로 asc의 top()요소를 옮긴다.
12. i가 홀수일 경우 desc의 top요소를 출력한다.
13. outs를 증가시키고, 증가시킨 값이 10이라면 개행문자를 삽입하고 outs을 0으로 변경한다.
14. outs가 10이 아니라면 i가 m이 아닌 경우 공백을 기준으로 구분한다.
15. 테스트케이스가 종료된 후엔 개행문자를 삽입해준다.
16. 모든 테스트케이스가 완료될 때까지 해당 로직을 반복한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 각 출력 라인의 마지막에 공백이 있으면 출력이 알맞지 않은 상태로 채점되는 것 같다.
2. 최대 힙과 최소 힙의 사이에 있는 요소 한개가 중앙값이된다.

 

정답 코드

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

int t, m;

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

	cin >> t;
	while (t--) {
		cin >> m;
		cout << (m + 1) / 2 << "\n";
		priority_queue<int, vector<int>, greater<int>> asc;
		priority_queue<int> desc;

		int outs = 0;
		for (int i = 1; i <= m; ++i) {
			int a; cin >> a;
			if (desc.empty()) desc.push(a);
			else if (asc.empty()) asc.push(a);
			else if (desc.top() > a) desc.push(a);
			else asc.push(a);

			if (!desc.empty() && !asc.empty() && desc.top() > asc.top()) {
				asc.push(desc.top());
				desc.pop();
			}

			if (desc.size() > asc.size() + 1) {
				asc.push(desc.top());
				desc.pop();
			}
			else if (desc.size() < asc.size()) {
				desc.push(asc.top());
				asc.pop();
			}

			if (i % 2) {
				cout << desc.top();
				if (++outs == 10) {
					cout << "\n";
					outs = 0;
				}
				else if (i != m) cout << " ";
			}
		}
		cout << "\n";
	}
}