[프로그래머스/Python] 이중우선순위큐 - Level3

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

import heapq

def solution(operations):
    heap = []
    
    for operation in operations:
        o = operation.split(' ') # 명령어 값 분리하여 저장
        
        # 명령어에 따라 처리하는 부분
        if o[0] == 'I': heapq.heappush(heap, int(o[1])) #명령어가 'I 숫자'인 경우
        else:
            if len(heap) > 0:
                # 명령어가 'D 1'인 경우
                if o[1] == '1': heap.pop(heap.index(heapq.nlargest(1, heap)[0]))
                # 명령어가 'D -1'인 경우
                else: heapq.heappop(heap)
    
    # 최대값, 최소값 리턴
    if heap: return [heapq.nlargest(1, heap)[0], heapq.nsmallest(1, heap)[0]]
    else: return [0, 0]

이 문제는 그렇게 어렵지는 않아서 레벨2 정도 수준이었던 것 같다.

입력으로 받은 명령어들을 하나씩 가져와서 명령어의 값을 확인해야 한다. 명령어 리스트(operations) 에서 명령어(opertaion)을 가져와 명령어를 분리하여 o에 리스트로 저장한다. 예를 들어 명령어가 'I 8' 이라면 o = ['I', '8'] 이 된다. 명령어를 가져왔다면 명령어에 따른 처리를 해주게된다. 그 부분이 if - else문으로 짜여있다. len(heap) > 0 조건이 없으면 indexError 가 발생하므로 꼭! 확인해줘야 하는 조건이다.

 

- 명령어가 'I 숫자'인 경우 명령어의 첫번째 값(o[0])이 I라면 힙에 숫자(o[1])를 저장한다.

- 명령어가 ' D 1'인 경우 힙에서 최대값을 삭제한다. 이 코드에서 힙이 최소힙으로 되어있기 때문에 pop을 하면 최소값이 삭제된다. 따라서 최대값을 삭제하기 위해서는 힙에서 nlargest()를 사용하여 최대값을 구한 후 최대값의 위치를 찾아 그 위치에 있는 값을 삭제하면 된다.

- 명령어가 'D -1'인 경우 힙에서 최소값을 삭제한다. 최소힙이므로 힙에서 pop을 하면 최소값이 삭제된다.

 

마지막으로  최대값, 최소값을 리턴해주어야 하는데 힙에 남아있는 값이 없을 수 있으므로 if - else 문을 사용해 처리해준다. heap에 값이 있다면 최대값과 최소값을 리턴해주고 그렇지 않다면 [0, 0] 을 리턴해준다.

 

- 배운 점 -

① heapq.nlargest(n , iterable)

- 데이터 집합(iterable)에서 n개의 가장 큰 요소로 구성된 리스트를 반환

 

② heapq.nsmallest(n, iterable)

- 데이터 집합(iterable)에서 n개의 가장 작은 요소로 구성된 리스트를 반환