[LeetCode] 295. Find Median from Data Stream (C++)

문제

 

https://leetcode.com/problems/find-median-from-data-stream/description/

Find Median from Data Stream - LeetCode

 

 

풀이

 

난이도: Hard

 

 

우선순위 큐(구현체는 Heap)를 통해 해결해 보자.

 

문제를 해결하기 위해 두 가지 우선순위 큐를 유지한다.

 

1. 하나는 중간 값보다 작거나 같은 값을 절반 가지고 있고, 이 큐는 top에 가장 큰 값을 유지한다. (small_half_pq)

2. 다른 하나는 중간 값보다 큰 값을 절반 가지고 있고, 이 큐는 top에 가장 작은 값을 유지한다. (large_half_pq)

 

이때 삽입되는 수가 홀수라면 절반씩 가지고 있을 수 없기 때문에, 홀수일 때는 small_half_pq의 크기가 하나 더 크게 유지하자.

 

 

 

들어오는 수로 전체 개수가 홀수

새로운 수가 들어오기 전에 전체 개수(n)가 짝수라면, 이번에 들어오는 수로 전체 개수가 홀수가 된다.

따라서  small_half_pq에 하나를 크게 유지하자.

 

1. 새로운 수를 large_half_pq에 넣는다. (small_half_pq.size == n/2), (large_half_pq.size == n/2 +1)

2. large_half_pq.top을 small_half_pq로 옮긴다. (small_half_pq.size == n/2 +1), (large_half_pq.size == n/2)

 

large_half_pq.top은 중간 값보다 큰 값 중에서 가장 작은 값이다.

이 값이  small_half_pq로 옮겨지면 바로 small_half_pq.top이 되고, 이 값이 Median 값이다.

 

 

 

 들어오는 수로 전체 개수가 짝수

새로운 수가 들어오기 전에 전체 개수(n)가 홀수라면, 이번에 들어오는 수로 전체 개수가 짝수가 된다.

지금은 small_half_pq가 한개 크기 때문에, 두 우선순위 큐의 균형을 맞춰주자.

 

1. 새로운 수를 small_half_pq에 넣는다. (small_half_pq.size - 2 == large_half_pq.size)

2. small_half_pq.top을 large_half_pq로 옮긴다. (small_half_pq.size == large_half_pq.size)

 

small_half_pq.top은 중간 값보다 작거나 같은 값 중에서 큰 값이다.

이 값이 large_half_pq로 옮겨지면 바로 large_half_pq.top이 된다.

 

 

 

두 가지 우선순위 큐를 이와 같은 방식으로 유지하면

홀수일 때는 small_half_pq.top이 Median 값이되고

짝수일 때는 두 가지의 top을 합쳐 2로 나누면 Median 값이 된다.

 

 

 

코드