파이썬_고득점키트_문제풀이(5)-힙정렬-더맵게

작성일 | In

5. 힙(Heap)- 더 맵게

  • 힙이란 것의 성질만 알면 쉬운 문제다.

  • 힙을 응용하는 방법의 기초

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

  • n개의 수 중 가장 작은 수 + 두 번째로 작은 것을 가장 작은 것 + 두 번쨰로 작은 것 *2 해서 새로 만들어서 모든 수가 특정한 수 k를 넘을 때까지 하려면 더하는 일을 최소 몇번 해야하는 지 알아내라

  • 제한사항
  • scoville의 길이는 1이상 10만 이하
  • k는 10만 이하
  • scoville의 길이가 0이상 10만 이하
  • 모든 음식의 스코빌 지수를 k 이상으로 만들 수 없는 경우에는 -1을 출력한다.

문제의 해결 예제

  • 1 2 3 9 10 12 , k = 7

  • 정렬되어 있지 않다면, 정렬을 해야 한다.

  • 1+ 2*2 = 5

  • 이 5를 다시 음식 목록에 집어 넣어야 하는데, 5가 들어갈 자리는. 3,9사이에 넣어야 한다
  • 3 5 9 10 12
  • 3 + 5*2 = 13
  • 9 10 12 13이 된다.
  • 제일 작은 9가 이미 7 이상이기 때문에, 지금까지 몇 번이나 스코빌 지수 계산을 했는지 세서 반환한다.

알고리즘의 복잡도

  • 최악의 경우 - 수가 하나 남을 때까지 섞어야 하는 경우 (n-1)회
  • 각 단계 (“섞는 일”)에서 요구되는 계산량 (섞어서 새로 만들어진 음식이, 정렬된 배열내에 어느 위치에 들어가야 하는지, 그 때 요구되는 계산량)
    • 정렬된 리스트에 순서 맞추어 원소 삽입 (리스트의 길이에 비례)
    • O(n)
  • 전체 문제 풀이의 복잡도 : n번의 단계를 거치는데, O(n^2)의 복잡도를 가진다. (자세하게 계산하면 n^2/2가 되겠지만.)
  • 뭔가 더 좋은 방법은 없을까?

보다 나은 방법

  • 최소/ 최대 원소를 빠르게 꺼낼 수 있으면 좋겠는데.
  • 힙
    • max heap
    • min heap

힙

  • 성질 : 최대/ 최소 원소를 빠르게 찾을 수 있음
  • 연산
    • 힙 구성 (heapify) -O(Nlog N) (N개의 원소를 삽입하는데에는 Nlog N)
    • 삽입 (insert) - O(log N)
    • 삭제 (remove) - O(log N)

힙의 구현

  • 완전 이진 트리로 구현하는 것이 일반적이다.
    • 배열을 이용해서 구현 가능해진다.

힙의 응용

  • 정렬 (heapsort)
  • 우선 순위 큐 (priorityQueue) - 큐에서 빠져 나오는 데에는 우선 순위에 따라 나오기 때문에.

구현

  • python에서 힙 적용
  • import heapq (q가 붙은 이유는 priorityQueue의 성질을 갖기 때문)
  • heapq.heapify(L) - 리스트 L로부터 minheap 구성
  • m = heapq.heappop(L) - min heap L에서 최소값 삭제 (반환)
  • heapq.heappush(L,x) - min heap L에서 원소 x삽입

코드

import heapq

def solution(scoville,K):
    answer = 0
    heapq.heapify(scoville) # scoville을 minheap으로 만든다
    while True:
        # 중단 조건은 2가지
        # 모든 scoville의 원소가 k이상이 되었거나
        # 음식이 하나 밖에 안남았는데, scoville가 k에 이르지 못한 경우
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        elif len(scoville) == 0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1+min2*2
        heapq.heappush(scoville,new_scoville)
        answer += 1
    return answer
  • 코드의 복잡도
  • 6번 행의 while True. 이 loop은 전체의 반복을 이룸
  • 이 루프는 최대 몇번까지 ? -> 즉 최대 1번 반복할 때, 원소의 개수가 하나씩 줄어든다. 즉 n-1번 반복
  • 대충 최악의 경우 n이라고 한다면 7행의 heap에 대한 pop, 13행의 pop연산이 들어있다. 각각은 원소의 길이가 n이라면 logn에 비례한다
  • 새로운 원소를 삽입하는 연산도 원소의 길이가 n이라고 하면 logn에 비례
  • 따라서 전체 알고리즘의 복잡도는 n (전체 알고리즘 loop)* log n(각 단계) => n log n

참고_heapq 모듈 사용방법

  • heapq 모듈을 통해서 원소를 추가하거나 삭제한 리스트가 그냥 최소 힙
  • heap에 원소 추가 heappush()
  • heap에 원소 삭제 heappop()
  • 최소값 삭제하지 않고 얻기 print(heap[0]
  • 기존 리스트를 힙으로 변환 heapq.heapify(heap)
  • 최대 힙: 튜플을 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리 이용
    • (우선순위, 값)구조의 튜플을 힙에 추가하거나 삭제한다.
import heapq
nums = [4,1,7,3,8,5]
heap = []

for num in nums:
    heapq.heappush(heap,(-num,num))
while heap:
    print(heapq.heappop(heap)[-1])
  • k번째 최소값/ 최대값 : k번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop()함수를 k번 호출하면 된다.
  • 힙 정렬: heap 배열에 정렬 해놓고, pop을 sorted_nums 배열에 넣어주면 된다.

참고자료 [프로그래머스]https://programmers.co.kr/learn/courses/9877 [heapq모듈사용방법]http://www.daleseo.com/python-heapq/

0%