백준 BOJ 2696 - 중앙값 구하기

벡터를 써서 적당히 풀었다.

확실히 여름학교 개념이 좀 도움이 되긴 한거같다.

남은날이 힘들어도 이렇게 문제가 잘 풀린다면 참고 잘 견딜 수 있을 거 같다.

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

2696번: 중앙값 구하기

입력받을때마다 매번 재정렬하는건 너무 시간낭비가 심해서

항상 정렬되있게끔 적당히 값을 사이사이에 끼워넣어줄것이다

그걸 위해서 std::vector의 insert함수를 이용하겠다.

​

사실 std::multiset으로 하는게 편할거같긴 한데

multiset은 인덱스 접근이 안되기 때문에 이렇게했다.

 

#include <stdio.h>
#include <vector>

using namespace std;

vector<int> v;
vector<int> print;

int insert(int s, int e, int k){
	if(s==e){
		v.insert(v.begin()+s, k);
		return 0;
	}
	if(v.size() == 0) v.push_back(k);
	else{
		int mid = (s+e)/2;
		if(v[mid] > k) return insert(s, mid, k);
		else return insert(mid+1, e, k);
	}
}

int main(){
	int t,n,tmp;
	scanf("%d", &t);
	while(t--){
		print.clear();
		scanf("%d", &n);
		for(int i=0; i<n; i++){
			scanf("%d", &tmp);
			insert(0,i,tmp);
			if(i%2==0) print.push_back(v[i/2]);
		}
		printf("%d\n", print.size());
		for(int i=0; i<print.size(); i++){
			if(i%10 == 0 && i!=0) puts("");
			printf("%d ", print[i]);
		}
		puts("");
	}
	return 0;
} 

int insert() 함수는 파라메트릭 서치를 하며 넣을 위치를 찾는다.

넣을 위치를 찾은경우(s==e이다), 그 자리에 insert 함수를 통해 값을 넣어

결과적으로 vector이 항상 정렬될수 있도록 해주었다.

​

그리고 중앙값의 개수를 구해야 하기 때문에 따로 print라는 벡터를 만들어

값을 계산할때마다 저장해두었고,

print.size()함수를 이용해서 개수를 출력해준 다음

10개씩 자르라는 말이 있었으므로

잘라주는 부분까지 잘 처리해주면 AC를 받을 수 있다.

​

​