[백준 2696번] 중간값 구하기

난이도: 골드 II

문제 링크: https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

백준 2696번 문제 중앙값 구하기

 

입력받은 n개의 정수 (n은 홀수) 중, 차례로 읽으며 홀수번째 수를 읽을 때마다 그 수까지의 중간값을 출력하는 문제입니다.

가장 먼저 떠오른 생각은... 매 홀수번째 수를 읽을 때마다, 지금까지 읽은 수를 정렬한 후 중간값을 읽자... 인데

그러면 원소의 개수가 n개라면 총 (n/2)번 정렬을 해야 합니다. Quick sort가 평균 n log n의 시간 복잡도를 가지므로, 총 n^2 log n의 시간복잡도가 되는데... n은 최대 9999이므로 주어진 제한시간인 1초 이내에 수행할 수 없습니다.

 

제가 생각한 방법은 두 개의 priority queue를 사용하는 것입니다.

heap 기반 priority queue의 삽입 시간 복잡도는 log n이므로, 총 n개의 원소에 대해 n log n의 시간복잡도를 가집니다.

첫 번째 pq는 max_pq라고 합니다. 숫자가 내림차순으로 정렬되며 (즉 max_pq.top()은 가장 큰 원소를 가리킴), 중간값 및 중간값 이하의 값이 저장됩니다.

두 번째 pq는 min_pq라고 합니다. 숫자가 오름차순으로 정렬되며 (즉 max_pq.top()은 중간값보다 크거나 같은 원소 중 가장 작은 원소를 가리킴), 중간값 이상의 값이 저장됩니다.

 

원소를 읽으며 다음과 같이 진행합니다.

 

1. max_pq, min_pq가 둘 다 비어있는 경우 (초기 상태)

• 현재 원소를 max_pq에 넣습니다.

2. max_pq의 크기가 min_pq의 크기보다 큰 경우 (max_pq.size() > min_pq)

• 현재 원소가 중간값보다 작은 경우
  • 현재 중간값을 min_pq로 옮깁니다.
  • 현재 원소를 max_pq에 넣습니다.
• 그렇지 않은 경우 (현재 원소가 중간값과 같거나 큰 경우)
  
  • 현재 원소를 min_pq에 넣습니다.

3. max_pq의 크기가 min_pq의 크기와 같은 경우 (max_pq.size() == min_pq)

• 현재 원소가 중간값보다 큰 경우
  
  • 중간값을 min_pq로 옮깁니다.
  • 현재 원소를 max_pq에 옮깁니다.
• 그렇지 않은 경우 (현재 원소가 중간값과 같거나 작은 경우)
  • 현재 원소를 max_pq에 넣습니다.

 

이를 코드로 구현하면 아래와 같습니다.

 

 

결과

 

삽입 시에 정렬이 되는 자료구조를 어떻게 이용하여 풀 수 있을지 고민해야 하는 문제였습니다.