프로그래머스 고득점 Kit(Python) - 3. 힙

힙(HEAP)

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공

import heapq
heap = []
heapq.heappush(heap, 4) # 4 삽입
print(heapq.heappop(heap)) #삭제하면서 최소값 얻기
print(heap[0]) #삭제하지않고 최소값 얻기
# 일반 리스트 -> heap으로 변경 : heapq.heapify
heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)

참고 : https://www.daleseo.com/python-heapq/

더 맵게

heapq 모듈 사용해서 스코빌지수 섞어서 계산

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] <K :
        if len(scoville)==1:
            return -1
        mixed = heapq.heappop(scoville) + heapq.heappop(scoville)*2
        heapq.heappush(scoville, mixed)
        answer += 1
    return answer

디스크 컨트롤러

아이디어 : temp에서 걸리는시간 적은순으로 처리 & jobs에서 요청시작시간 만족하는 값들을 temp에 넣기 반복
temp : 걸리는시간 순으로 정렬된 heapq
jobs : 요청시작시간 순으로 정렬된 heapq
while : 힙큐 h에서 제일 처리시간이 짧은 것을 가져와서 처리
아직 처리할 일들이 남아있다면
1. 현재 시작시간(count) 보다 요청시작시간이 빠르면 h에 넣는다
2. 현재 시작시간보다 뒤에 요청이 들어오지만 h에 아무것도 없다면
현재 시작시간(count)를 unknown의 요청시작시간으로 맞추고 값을 h에 넣는다
3. 그외라면 아직 시작요청이 들어오지 않은 상태이므로 다시 jobs에 넣는다

import heapq

def solution(jobs):
    total = 0
    length = len(jobs)
    heapq.heapify(jobs)
    temp = heapq.heappop(jobs)
    h = [[temp[1],temp[0]]]
    count = temp[0]
    
    while h or jobs:
        # print(jobs,h,total,count)
        last, start = heapq.heappop(h)
        total += count - start + last
        count += last
        
        while jobs:
            unknown = heapq.heappop(jobs)
            if unknown[0] <= count:
                heapq.heappush(h,[unknown[1],unknown[0]])
            elif not h:
                heapq.heappush(h,[unknown[1],unknown[0]])
                count = unknown[0]
            else:
                heapq.heappush(jobs,unknown)
                break

    # print(jobs,h,total,count)     
    return int(total/length)

이중우선순위큐

명령어에 따라 삽입/삭제 진행
sorted를 통해 오름차순으로 정렬하고 최소/최대값을 제거하였다

def solution(operations):
    h = []
    for oper in operations:
        current = oper.split(" ");
        
        if current[0]=="I": # 삽입
            h.append(int(current[1]))
        elif current[0] == "D":
            number = int(current[1])
            if number > 0 : # 최댓값 삭제
                h = sorted(h)[:-1]
            else: # 최솟값 삭제
                h = sorted(h)[1:]
    h.sort()
    if len(h)==0: return [0,0]
    else:    return [h[-1],h[0]]

h = heapq.nlargest(len(h), h)[1:]
heapq.nlargest(개수, 배열)
=> 배열에서 큰 값순으로 개수만큼 배열을 정렬해줌
heapq.nlargest(len(h), h)
=> h 배열을 len(h) 개수만큼 숫자 큰 순서대로 정렬
h = heapq.nlargest(len(h), h)[1:]
⇒ 숫자 큰 순서대로 정렬한 배열에서 0번째 인덱스값 제거(제일 큰값 제거)한 배열을 h에 넣어줌
현재 h는 숫자 큰 순서대로 정렬되어 있으므로 heap정렬 다시 해줘야함
heapq.heapify(h)

import heapq

def solution(operations):
    h = []

    for operation in operations:
        op, val = operation.split()

        try:
            if op == 'I':
                heapq.heappush(h, int(val))
            elif val == '-1':
                heapq.heappop(h)
            else:
                h = heapq.nlargest(len(h), h)[1:]
                heapq.heapify(h)
        except:
            continue

    if h:
        return [max(h), min(h)]
    else:
        return [0, 0]