23.03.02 파이썬 코딩 퀴즈#180 이중순위우선큐(프로그래머스 스쿨)

이번 문제는 이중우선순위큐 문제이다.

먼저 문제 설명을 확인해 보자.

명령어는 총 3개가 존재한다

I 숫자 = 큐에 주어진 숫자를 삽입해야 한다.

D 1 = 큐에서 최댓값을 삭제해야 한다.

D -1 = 큐에서 최솟값을 삭제해야 한다.

그리고 최종적으로 모든 연산을 처리한 큐가 비어 있다면 [0,0] 을, 그렇지 않다면 [최댓값, 최솟값]을 return 해야 한다.

입출력 예를 통해 다시 한번 확인해보자.

먼저 입출력 예 1

"I 16" 에 의해 q = [16] 이 된다. (Insert 16)

"I -5643" 에 의해 q = [16, -5643] 이 된다. (Insert -5643)

"D -1" 에 의해 q = [16] 이 된다.(Delete 최솟값 -5643)

"D 1"에 의해 q = [] 이 된다. (Delete 최댓값 16)

"D 1"을 명령어로 받지만 q는 이미 비어있다.

"I 123"에 의해 q = [123] 이 된다. (Insert 123)

마지막으로 "D -1"에 의해 q = [] 이 된다. (Delete 최솟값 123)

따라서 최종적으로 q는 비게되고 [0,0]을 return 한다.

 

바로 코드로 작성해 보았다.

문제는 heap 으로 분류되어 있지만, operations의 길이가 백만이하 이기 때문에 그냥 arr를 사용하기로 하였다.

조건문에 의해 총 3단계로 나누어 지고, q가 있는 경우에만 "D" 연산을 수행하기에 시간에 영향을 덜 받는듯 하다.