[프로그래머스] 이중우선순위큐

문제

접근 방식

오늘은 간단한 문제 하나를 들고 왔다. 문제 분류는 힙(heap)으로 되어 있지만, 힙에 대해서 잘 몰랐던 나는 일단 이진 탐색이 바로 떠올랐고 30분 안짝으로 풀었다. 그래도 문제의 의도대로 풀어야지 하고 힙에 대해서 공부한다음 Max Heap까지는 구현하였지만, Heap의 성질이 부모 노드가 자식 노드보다 크거나 같기만 하면 되고 같은 부모 노드의 자식 노드끼리는 원래 값을 비교해 줄 필요가 없기 때문에 거기서 다시 sort를 하려면 코드가 더 필요하고, 노드 삽입과 삭제 구현 역시 더 추가 코드가 필요했으므로 결국 나는 Max heap을 구현한 것에 만족하고 heap sort로 구현하는 것은 포기.

정답 코드

이진 탐색으로 풀었기 때문에 시간 복잡도도 O(logN)이다.

* 시간 복잡도