Heap (개념 및 프로그래머스 문제)

힙(Heap)이란?

힙 트리(Heap Tree), 보통 줄여서 힙(Heap)이라고 부른다.

힙은 부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다.

트리의 일종으로 완전 이진 트리이면서, 부모 노드의 값이 항상 하위 노드의 값보다 작거나 큰 구조의 트리이다.

힙의 사전적인 의미가 '쌓아 올린 더미'인 것 처럼, 데이터가 위에서부터 규칙적으로 쌓여있는 구조이다.

 

 - 우선순위 큐를 위하여 만들어진 자료구조

 - 여러 개의 값 중 최댓값과 최솟값을 빠르게 찾기위한 구조

 - 부모 노드의 값이 자식 노드의 키 값보다 항상 큰 이진트리 

 - 힙은 중복된 값을 허용

 

종류 

 

최대 힙 Max Heap

1. 부모 노드의 값이 항상 하위 노드의 값보다 크거나 같다.
2. 부모_key >= 자식_key

최소 힙 Min Heap

1. 부모 노드의 값이 항상 하위 노드의 값보다 작거나 같다.
2. 부모_key <= 자식_key

 

프로그래머스 - Heap 

1번. 더 맵게

코딩테스트 연습 - 더 맵게

# Heap_1.py
# 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
import heapq
scoville = [1, 2, 3, 9, 10, 12]
K = 7


def solution(scoville, K):
    heapq.heapify(scoville)
    answer = 0

    while scoville[0] < K:
        if len(scoville) < 3:
            if K > scoville[1] + scoville[0]:
                return -1
            else:
                return answer + 1
        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)
        answer += 1
    return answer


print(solution(scoville, K))

 

2번. 디스크 컨트롤러

코딩테스트 연습 - 디스크 컨트롤러

# Heap_2.py 디스크 컨트롤러
# [[0, 3], [4, 3], [10, 3]] - 3
# [[0, 10], [2, 3], [9, 3]] - 9
# [[1, 10], [3, 3], [10, 3]] - 9
# [[0, 10]] - 10
# [[0, 10], [4, 10], [5, 11], [15, 2]] - 15
# [[0, 1], [1, 2], [500, 6]] - 3
# [[0, 9], [0, 4], [0, 5], [0, 7], [0, 3]] - 13
# [[0, 5], [1, 2], [5, 5]] - 6
jobs = [[0, 3], [1, 9], [2, 6]]


def solution(jobs):
    answer = 0
    start = 0
    length = len(jobs)  # 중간에 pop 할꺼기 때문에 미리 기록
    jobs = sorted(jobs, key=lambda x: x[1])

    while len(jobs) > 0:
        for i in range(len(jobs)):
            if jobs[i][0] <= start:  # start < 시작 초  : 처음 0초 다음 3초
                start += jobs[i][1]     # 처음 3초가됨
                answer += start - jobs[i][0]    # 작업이 진행된 초 - 들어온 초 => 진행 시간
                jobs.pop(i)
                break
            if i == len(jobs) - 1:
                start += 1  # 1초가 흐름

    return answer // length     # 전체 시간 나누기 길이의 몫


print(solution(jobs))

이거 어렵다..

 

3번. 이중우선순위큐

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

# Heap_3.py
operations = ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
# ["I 7", "I 5", "I -5", "D -1"]   # ["I 16", "D 1"]


def solution(operations):
    import heapq

    def operator(string, answer):
        word = string.split()
        if word[0] == "I":
            heapq.heappush(answer, int(word[1]))
        elif word[0] == "D":
            if answer:
                if word[1] == "-1":
                    heapq.heappop(answer)
                elif word[1] == "1":
                    answer.pop(answer.index(heapq.nlargest(1, answer)[0]))
        return answer

    answer = []
    for op in operations:
        answer = operator(op, answer)
    if len(answer) == 1:
        if answer[0] <= 0:
            return [0, answer[0]]
        else:
            return [answer[0], 0]
    elif answer:
        return [heapq.nlargest(1, answer)[0], answer[0]]
    else:
        return [0, 0]


print(solution(operations))