[PROGRAMMERS] 프로그래머스 코딩테스트 연습 > 힙(heap) 파이썬 문제풀이

프로그래머스 코딩테스트 연습 > 고득점 kit > 힙(heap) 파트 문제풀이 파이썬 https://programmers.co.kr/learn/courses/30/parts/12117

프로그래머스

 

 

힙(Heap)

출처 https://www.geeksforgeeks.org/heap-data-structure/

 

최대값과 최소값을 빠르게 찾기 위해 고안된 자료구조

각 노드의 key가 해당 노드의 자식노드의 key보다 작지 않거나(최대힙) 크지 않은(최소힙) 완전 이진트리

* 이진트리(binary tree) : 각 노드가 최대 2개의 자식을 갖는 트리구조

* 완전 이진트리(complete binary tree) : 두 개의 자식만 갖는 이진 트리 중 왼쪽부터 차례대로 채워진 트리

 

키 값의 대소관계는 부모-자식 노드 사이간에만 성립하며 형제 노드사이에는 영향을 미치지 않음

 

최대힙(Max Heap) : 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙, key(T.parent(v)) > key(v)

최소힙(Min Heap) : 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙, kye(T.parent(v)) < key(v)

 

시간복잡도

힙 정렬 O(n * log n)

삽입, 삭제 O(log n)

- 삽입 연산 : 트리의 가장 마자막에 원소 추가 -> 부모노드와의 대소비교를 통해 조건을 만족할때까지 자리 교환

- 삭제 연산 : 루트 노드 삭제 -> 가장 마지막 노드 루트로 이동 -> 자식노드와 비교하여 조건을 만족할때까지 자리 교환

 

 

 

파이썬 heapq 모듈

0) 모듈 import

import heapq

* 기본적으로 최소힙으로 구성

1) 힙 생성 & 노드 추가(heappush)

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap) # 10 50 20

1-1) 이미 존재하는 리스트 힙으로 변환(heapify)

heap = [50 ,10, 20]
heapq.heapify(heap)

print(heap) # 10 50 20

2) 가장 작은 노드 삭제 후 반환

result = heapq.heappop(heap)

print(result) # 10
print(heap) # 20 50

3) 인덱스를 통해 접근 가능

heap[0] # 20
heap[1] # 50

4) 최대힙 생성

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item)) # 튜플로 변환하여 삽입

print(max_heap)

* (-item, item)의 튜플 형태로 넣어주면 튜플의 첫번째 원소를 우선순위로 힙 구성, 원소의 부호를 바꿨기 때문에 크기 순서가 반대로 정렬되어 최소힙이 아닌 최대힙으로 구현

 

4-1) 최대힙 삽입

new_item = 11
heapq.heappush(max_heap, (-new_item, new_item))
print(max_heap) # [(-11, 11), (-7, 7), (-9, 9), (-1, 1), (-5, 5), (-3, 3)]

4-2) 최대힙 삭제

max_item = heapq.heappop(max_heap)[1]
print(max_item) # 11
print(max_heap) # [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]

* 튜플의 인덱스([1])를 통해 원래 값에 접근

 

 

더 맵게 (Level 2)

모든 음식이 주어진 스코빌 지수(k)보다 높아지도록 음식 조합

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

보기의 테스트케이스가 조금 부족해서 테스트 케이스를 조금 추가하였다

입력	출력
s, k = [1, 2], 3  s, k = [1, 2], 10	1  -1
s, k = [0, 0, 1], 1 (가장 작은 스코빌 지수는 0, 두번째로 작은 스코빌 지수도 0)  s, k = [0, 0, 1], 3	2  -1

 

 처음 생각했던 코드 

import heapq

def solution(scoville, K):
    answer = 0
    
    while True:
        min1 = heapq.heappop(scoville)
        if (len(scoville) == 0) & (min1 < K):
            return -1
        elif min1 < K:
            answer += 1
            min2 = heapq.heappop(scoville)
            heapq.heappush(scoville, min1 + min2 * 2)
        else:
            return answer

heappop으로 최소값을 빼면 데이터가 1개 남았을때 K와의 비교와 함수 종료 시점이 애매했다..

 

 내 두번째 코드 

def solution2(scoville, K):
    answer = 0
    
    while len(scoville) != 1:
        heapq.heapify(scoville)
        min1 = scoville[0]
        if min1 < K:
            answer += 1
            heapq.heappop(scoville)
            min2 = heapq.heappop(scoville)
            heapq.heappush(scoville, min1 + min2 * 2)
        else:
            return answer

    if scoville[0] > K:
        return answer
    return -1

heappop 대신 heap으로 구조를 바꿔 인덱스로 최소값을 하였고 1개의 데이터만 남았을때는 while문 밖에서 K와 비교하여 return값을 주었다.

이 코드는 테스트케이스는 다 통과했지만 효율성 테스트는 모두 실패,,

 

 내 세번째 코드 

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

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

    if scoville[0] > K:
        return answer
    return -1

while문 돌때마다 힙으로 바꾸는게 의미가 없을 것 같아 while문 돌기 전 heap으로 정렬해주었고 드디어 효율성 테스트 통과!

 

 다른 사람 코드 1

def solution(scoville, K):

    heapq.heapify(scoville)
    answer = 0
    while True:
        min = heapq.heappop(scoville)
        if min >= K:
            break
        if len(scoville) == 0:
            return -1
        min2 = heapq.heappop(scoville)
        heapq.heappush(scoville, min + min2 * 2)
        answer += 1  

    return answer

나와 거의 유사한 코드, while True로 시작하는 대신 안에 길이 비교문을 넣어 종료조건을 추가하였다.

 

 다른 사람 코드 2 

def solution(scoville, K):
    heapq.heapify(scoville)
    size, cnt = len(scoville) - 1, 0
    min = heapq.heappop(scoville)
    while size > 0:
        min = heapq.heappop(scoville)
        min2 = heapq.heappushpop(scoville, min + min2 + min2)
        if min >= K:
            return cnt + 1
        cnt += 1
        size -= 1
    return -1

 

대부분 다 비슷비슷하게 푼것 같다. 이번 문제는 다른 코드 참고 한번도 안하고 스스로 내가 풀었다!!!! 뿌듯 ㅎㅅㅎ

 

 

디스크 컨트롤러 (Level 3)

작업의 수행 시간이 리스트로 주어졌을 때 작업 완료까지의 평균 대기시간 최소값을 구하는 문제..

문제는 이해가지만 넘 어려워서 이건 그냥 다른 사람 코드 참고하여 풀었다(코드 이해도 오래걸린듯 ㅠ) 

 

 코드 1 

def solution(jobs):
    answer = 0
    now = 0 # 현재 시점
    length = len(jobs)

    jobs = sorted(jobs, key=lambda x: x[1]) # 작업 소요시간 기준 정렬

    while len(jobs) != 0:
        for i in range(len(jobs)): # jobs의 수가 줄어들면서 i는 계속 0
            if jobs[i][0] <= now: # jobs의 가장 맨 앞의 작업이 완료되면
                now += jobs[i][1] # 현재 시간 + 해당 작업 소요시간
                answer += now - jobs[i][0] # 총 대기시간 += 현재 시점 - 작업이 들어온 시점
                jobs.pop(i) # 해당 작업 삭제
                break

            if i == len(jobs) - 1: # 작업이 아직 끝나지 않으면
                now += 1

    return answer // length

 

 코드 2 

import heapq

def solution(jobs):
    count, last, answer = 0, -1, 0
    heap = []
    jobs.sort()
    time = jobs[0][0] # 현재 시점(첫번째로 들어온 작업은 가장 먼저 수행)
    
    while count < len(jobs):
        for s, t in jobs:
            if last < s <= time: # 작업 소요시간 기준 min heap, 계속해서 힙 감소
                heapq.heappush(heap, (t, s))
        
        if len(heap) > 0: # 바로 수행할 수 있는 작업이 있는 경우
            count += 1 
            last = time # 현재 시점
            term, start = heapq.heappop(heap) # 소요 시간, 들어온 시점
            time += term # 현재 시점 += 소요 시간
            answer += (time - start) # 총 대기시간 += 현재 시점(완료시간) - 들어온 시점
        else: # 바로 수행할 수 있는 작업이 없는 경우
            time += 1 
    return answer // len(jobs)

 

대충 알고리즘의 요점은 작업 소요시간 기준으로 오름차순 정렬하는 것과 지금 현재 시점 정보를 계속해서 갱신하여 계산에 이용하는 것, 그 밖에는 잘 모르겠다. 여전히 왜 소요시간 기준으로 정렬해야하는지 모르겠듬..

 

 

우선순위 큐 (Level 3)

level 3 문제들은 확실히 난이도가 있다.. 고로 나중에 추가할 예정..!