[코딩테스트 고득점 Kit] 힙(Heap) 이중우선순위큐

[문제 이해 및 풀이]

맨 처음에는 heapq를 사용해서 문제를 해결해야겠다고 생각했다.

우선 operations을 돌면서 하나씩 입력받으며 I이면 heap에 push해주고 숫자가 1이면 초대값을, -1이면 최소값을 출력해주는 코드를 짜려고 했다.

heap은 push해주는 과정에서 최소힙 혹은 최대힙으로 바로 정렬이 가능하기 때문에 그 방법을 했지만 최소힙으로 넣은 경우에는 최대값을 출력하는 과정에서, 최대힙으로 넣은 경우에는 최소값을 출력하는 과정에서 어려움을 겪었다.

그래서 우선 stack/que를 사용해보기로 하였다. delete명령을 받으면 list정렬을 해준 뒤 맨 처음 값 혹은 맨 마지막 값을 출력해주는 코드를 짰다.

제출을 한 뒤, heapq를 이용한 방법을 찾아보다가 remove를 활용하면 된다는 것을 알게 되었다.

heapq를 쓸꺼라고 해서 무조건 heapq에 내장되어 있는 함수만을 생각했던 게 문제였던 거 같다. heapq에서도 remove 사용할 수 있다 !!

 

---

[나의 코드]

def solution(operations):
    answer=[]
    lst=[]
    while(operations):
        oper,num=operations.pop(0).split()
        num=int(num)
        if oper=='I':
            lst.append(num)
        elif len(lst)>0:
            lst.sort(reverse=True)
            if num==1:
                lst.pop(0)
            else:
                lst.pop()
    if len(lst)==0:
        answer=[0,0]
    else:
        answer.append(max(lst))
        answer.append(min(lst))
    return answer

[수정 코드]

import heapq
def solution(operations):
    heap=[]
    while(operations):
        oper,num=operations.pop(0).split()
        num=int(num)
        if oper=='I':
            heapq.heappush(heap,num)
        elif heap:
            if num==-1:
                heapq.heappop(heap)
                print(heap)
            else:
                heap.remove(max(heap))
                print(heap)
    if len(heap)==0:
        return [0,0]
    else:
        return [max(heap),heap[0]]

---

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42628

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