백준 2696번 중앙값 구하기

문제

어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.

예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

문제풀이

사용한 알고리즘 : priority_queue

유사한 문제 : https://mapocodingpark.blogspot.com/2020/01/BOJ-1655.html

(1) 코드 12~13

 중앙값을 기준으로 중앙값보다 작은 값들을 저장할 priority_queue (: 큰 값이 위로), 

 큰 값들을 저장할 priority_queue ( : 작은 값이 위로 )를 만들어줍니다. 

(2) 코드 20~24

 첫 입력으로 들어오는 값을 중앙값으로 잡고, 다음 입력부터 중앙값보다 큰지 작은지를 판단하여 과정(1)에서 만들어 놓은 두 priority_queue에 저장해줍니다.

(3) 코드 26~38

 홀수번째 입력마다 중앙값을 알맞게 맞춰줘야 합니다.

 즉, 중앙값 기준, 작은 값들을 저장한 pq와 큰 값들을 저장한 pq의 사이즈가 같아야 합니다.

 한쪽 pq가 더 크다면, 두 pq의 사이즈가 같아질 때까지 중앙값을 사이즈가 작은 쪽에 넣어주고, 사이즈가 큰 쪽에서 값을 하나 빼서 해당 값을 중앙값으로 생각해줍니다.

(4) 주의

 한 줄에 10개까지만 출력해주어야합니다.