오늘의 학습 키워드

Heap

공부한 내용 본인의 언어로 정리하기

프로그래머스 42628

• 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현

• 'I' 숫자 큐에 주어진 숫자를 삽입합니다.

• 'D 1' 큐에서 최댓값을 삭제합니다.

• 'D -1'큐에서 최솟값을 삭제합니다.

어떤 문제가 있었고, 나는 어떤 시도를 했는지

def solution(operations):
    answer = []
    queue =[]
    for i in operations:
        # print(i)
        if i[0]=="I":
            queue.append(int(i[2:]))
        else:
            if queue ==[]:
                pass
            else:
                if i == "D 1":
                    queue.remove(max(queue))
                if i == "D -1":
                    queue.remove(min(queue))
        # print(i,queue)
    if queue ==[]:
        answer=[0,0]
    else:
        answer = [max(queue),min(queue)]
    # print(answer)
    return answer

• I 일 경우 : 인덱스 슬라이싱을 통해 append
• D 일 경우 (삭제일 경우) : remove 함수 통한 삭제
• 빈 리스트일 경우 [0,0] return, 아니면 최댓값, 최솟값 return

내 코드의 아쉬운점

1. heap 을 제대로 사용하지 않았다
2. 높은 시간 복잡도

다른 사람의 풀이

from heapq import heappush, heappop

def solution(arguments):
    max_heap = []
    min_heap = []
    for arg in arguments:
        if arg == "D 1":
            if max_heap != []:
                heappop(max_heap)
                if max_heap == [] or -max_heap[0] < min_heap[0]:
                    min_heap = []
                    max_heap = []
        elif arg == "D -1":
            if min_heap != []:
                heappop(min_heap)
                if min_heap == [] or -max_heap[0] < min_heap[0]:
                    max_heap = []
                    min_heap = []
        else:
            num = int(arg[2:])
            heappush(max_heap, -num)
            heappush(min_heap, num)
    if min_heap == []:
        return [0, 0]
    return [-heappop(max_heap), heappop(min_heap)]

• heapq 라이브러리를 통해 시간 복잡도를 죽였다
• max_heap == [] or -max_heap[0] < min_heap[0] 조건문을 통해 리스트 초기화

무엇을 새롭게 알았는지

heapq 사용

학습할 것은 무엇인지

• 11일차 과제
• heapq 개념 정리 및 활용 공부