[파이썬] 프로그래머스 커뮤러닝 2주차 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

 

 

스코빌 지수가 되었든, 아니든 수가 주어질 것이다. N개의 수중에 가장 작은 것과 두번 째로 작은수에 *2를 써서 더하는 것을 몇 번 해야되는지 알아내는 문제이다.

 

제한사항을 보면 효율성 테스트도 포함되어 있다.

 

정렬을 통해 1 부터 12까지 본다.

1과 2중 2에 x2를 해주면 5가 나오고 이것을 다시 원소의 순서대로 넣어줌

 

다시 반복을 실시한다

 

13의 경우, 가장 뒤에 있는 12보타 크므로 가장 뒤로 간다.

 

섞는 요구되는 계산이 있는데 이는 길이에 비례하여 계산이 된다.

 

과정이 복잡하기 때문에 연산량이 O(n2)으로 굉장이 높은 것을 알 수 있다.

이를 해결하기 위해 Heap 알고리즘 을 사용해야 한다.

 

 

최소 또는 최대 원소를 빠르게 꺼낼 수 잇는 원소가 있어야 된다.

 

 

 

힙

 

- 최대 또는 최소의 원소를 빠르게 찾을 수 있다. 가장 큰 원소가 어떤 원소인지 찾을 수 있다.

특징은 3가지 있는데,

힙 구성 : 힙의 연산을 위해 힙 자료구조를 만드는 연산을 실시한다.

삽입 : 임의의 원소를 집어 넣으며 삽입연산을 빠르게 구현할 수 있도록 한다.

삭제 : max heap이면 최대, min heap이면 최소의 원소를 빠르게 찾을 수 잇도록 내부 구조를 유지할 수 있도록 한다.

계산 복잡도는 log에 비례하는 복잡도를 가지게 되어 

4배 증가한다 해도 2배정도로 효율적인

 

 

힙의 구현 (max heap)

최대값 30은 루트 node를 본다면 가장 큰 값이라고 볼 수 있고, 어떤 모양을 가지고 트리를 구성하며, 배열을 이용해서 이를 구현이 가능하다.

 

힙의 응용

 정렬 - 임의의 순서로 주어졌을 때, 모든 원소를 삽입하고 N lon N 순서로 걸리고 remove하면 N lon N 의 계산복잡도가 되어지도록 한다. 

우선순위 큐 - 큐에 들어갈 때 아무 순서로 들어가도 되지만, 우선순위에 따라서 만들어지게 될때에도 힙을 사용하게 된다,

 

 

headq.heapify(L)을 전달하면, 어떤순서로 들어 있든간에, min heap을 구성하고 리스트 힙을 구성하여 List L에 min heap 구조를 가지게 된다.

m= heaq.heappop(L) 는 L에 들어있는 L 힙을 최소값이 없어지고, min heap구조를 유지하게 되어있다. 

heapq.heappush(L,x) 새로운 원소 X가 삽입되고 여전히 min heap의 구조를 가지게 되어있고, log N 만큼 소비해서 유지하고 log N 타임에 유지되도록 실시됨

 

 

사전풀이

import heapq

def solution(scoville, K):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    
    mix_cnt = 0
    while heap[0] <K:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        mix_cnt += 1
    return mix_cnt

 

Heap을 사용하지 않고 list 나 배열을 사용하게 된다면 N**2의 복잡도를 가지게 된다.