2696. 중앙값 구하기

오랜만에 문제를 풀었다. 그동안 생각이 좀 많았어서 ㅎㅎ..

2696번: 중앙값 구하기

---

너무 쉬워

그냥 매번 입력받으면서 정렬하면 그만 아닌가?

맞겠냐

한번 입력받고 정렬하는 데 대략 $MlogM$, 입력을 총 $M$번 받으므로 테스트 케이스 하나당 시간 복잡도는 $O(M^{2}logM)$이다. 테스트 케이스의 개수까지 고려하면 풀릴 리가 없다.

그럼 어쩔까요

당연히 더 효율적인 방법을 찾아야 한다. 사실 이 문제처럼 변하는 배열에서 중앙값을 구하고 싶을 때 유용한 테크닉이 있다. 우선순위 큐를 활용하는 방법이다.

 

우선순위 큐 2개를 준비한다. 하나(``left``)는 큰 수가 위로 오도록, 다른 하나(``right``)는 작은 수가 위로 가도록 정렬한다. 이름에서 알 수 있듯이 ``left``와 ``right``의 원소를 순서대로 쭉 이으면 하나의 정렬된 배열이 된다. 그러니까 대략 이런 식이다.

``size(left) = size(right) + 1``이라는 조건을 두면 중앙값을 ``left.top()``으로 쉽게 찾을 수 있다. 물론 ``right``의 크기를 더 크게 해도 된다. 이 경우 중앙값은 ``right.top()``이 된다.

 

이제 수를 하나씩 입력받으면서 조건에 맞게 ``left``와 ``right``를 조절하면 된다. 나는 우선 ``right``에 넣은 다음 ``size(left) = size(right) + 1``를 만족하도록 push와 pop 연산을 적용했다.

---

4ms?

사실 이 방법의 시간복잡도는  최악의 경우 $O(M^{2})$(오름차순 또는 내림차순으로 정렬된 배열이 주어지는 경우)이지만 통과되는 걸 보니 이 풀이가 맞는 모양. 

 

이 테크닉을 잘 기억하도록 하자.