[프로그래머스][heap] 힙 정렬(heap sort) 개념 + 더 맵게 python (200722)

1. 문제 설명 

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

 

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

 

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

 

* 제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

* 입출력 예시 

 

scoville               K          return

[1, 2, 3, 9, 10, 12]

7

2

 

* 입출력 설명 

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

 

 

2. 풀이 

1) 무작정 heap 을 사용하지 않고 풀기 (당연히~ 오답~!)

def solution(scoville, K):
    cnt = 0
    low_list, upper_list = [], []
    for i in scoville:
        if i < K:
            low_list.append(i)
        else:
            upper_list.append(i)
    low_list = sorted(low_list, reverse=True)

    i = 0
    while low_list:
        if len(low_list) != 1:
            if len(low_list) == 2:
                low_list = sorted(low_list, reverse=True)
            else:
                low_list[-3:] = sorted(low_list[-3:], reverse=True)
            mix_num = low_list[-1] + (low_list[-2] * 2)
            cnt += 1
            low_list.pop()
            low_list.pop()
        else:
            return -1
        if mix_num >= K: upper_list.append(mix_num)
        else: low_list.append(mix_num)

    return cnt

 

 

2) 힙 정렬 사용하기!!! 

 

 

힙 정렬 (heap sort) 란?

 

• 트리구조 부모의 값이 자식보다 크거나 같음 =⇒ 최대힙 (루트가 최대값)
• 반대로 자식보다 작거나 같음 =⇒ 최소힙 (루트가 최소값)
• (좌) 최대힙, (우) 최소힙

최대힙

 

⇒ 이 경우, 우선 순위 큐가 가능해진다.

   우선순위 큐는 - 최소값, 최대값을 찾아내는 연산을 빠르게 하기 위해 고안된 방식

 

=> 앞으로! 변경되는 숫자 리스트를 계속 정렬하며 최대값, 최소값을 구해야하는 문제라면

    python list 의 min max 를 활용해 매번 구하는게 아니라 (해당 경우 o(n) time complexity)

    애당초 최소 최대값이 뽑히게 하는 힙구조를 활용한다. 

 

 

python heapq 모듈 사용하기.

https://docs.python.org/3/library/heapq.html

heapq.heappop(heap)	힙의 불변성을 유지하면서 힙에서 가장 작은 항목힙이 비어있으면, 인덱스 에러뽑지 않고 접근만하려면 heap[0] 으로
heapq.heappushpop(heap,value)	value 값을 넣고, 가장 작은 항목을 poppush(),pop() 각각하는것 보다 효율적임
heapq.heapify(list)	리스트 를 힙으로 변환 time complexity : o(N)

 

그럼 힙으로 푼다면 (아주 쉬워짐)

 

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

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

0) while 문에서 조건은 scovile에서 가장 작은 값이 K 보다 작으면 (섞어야 할 게 있다면)

1) 가장 작은수 두개 heappop 으로 뽑은 다음 섞고 heappush로 넣어줌 (넣은 숫자는 힙구조에 의해 크기에 맞게 정렬됨) /그리고 cnt 1 증가

2) 만약 남은 길이가 1이 되면 --> 더이상 섞어서 더맵게 못만드니까 return -1

 

 

3.

힙 좋다.. 왜 여태껏 힙으로 안풀었지, 다른 스택/큐 문제들도 힙으로 풀 수 있지 않을까?

애니웨이 앞으로 숫자 정렬 + 변경 + 최대/최소 값 반환 문제 유형은 무조건 힙으로 조지자 !