C++ / 백준 / 2696 / 중앙값 구하기

문제

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

2696번: 중앙값 구하기

문제풀이

multiset을 이용하여 풀었다.

입력받으면 multiset에 집어넣고 홀수번째 수를 입력받을 때마다 iterator을 이용하여 한 칸씩 중앙값을 가리킬 때까지 iterator를 증가시키고 해당 값을 answer에 push 한다.

모든 입력을 받았으면 answer의 크기와 answer의 모든 값들을 출력한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int T(0), M(0);
	int idx(0), idx2(0), num(0);
	cin >> T;

	while (T--) {
		cin >> M;
		multiset<int>ms;
		multiset<int>::iterator iter;
		vector<int>answer;

		for (idx = 0; idx < M; ++idx) {
			cin >> num;
			ms.insert(num);
			iter = ms.begin();
			if (idx % 2 == 0) {
				for (idx2 = 0; idx2 < ms.size() / 2; ++idx2) {
					iter++;
				}
				answer.push_back(*iter);
			}
		}
		cout << answer.size() << '\n';
		for (idx = 0; idx < answer.size(); ++idx) {
			cout << answer[idx] << ' ';
		}
		cout << '\n';
	}

}