[Python] 프로그래머스, 더 맵게 Lv.2 (feat.heapq, min heap, 힙, 우선순위 큐, 파이썬)

반짝반짝 알고리즘, 인프준

 
 
 
 
 
 
 
 
 
 

더 맵게

문제 링크

프로그래머스

 

 

문제 설명

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

🔍 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + ( 두 번째로 맵지 않은 스코빌 지수 x 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 x 2 ) = 5
가진 음식의 스코빌 지수 = [ 5, 3, 9, 10, 12 ]

 
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

새로운 음식의 스코빌 지수 = 3 + ( 5 x 2 ) = 13
가진 음식의 스코빌 지수 = [ 13, 9, 10, 12 ]

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

---

 
 
 
 
 
 

해결 과정

'더 맵게' 문제는 프로그래머스 코딩테스트 고득점 Kit에서 힙(Heap)에 속해있는 문제입니다. 힙은 특정한 규칙을 가지는 트리로, 힙을 이용해서 우선순위 큐를 구현할 수 있습니다.
 

✓ 힙, Heap
최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 비선형 자료구조
루트 노드에 최소 값 or 최대 값을 저장하고 있는 완전이진트리( 마지막을 제외한 모든 노드가 자식 노드로 채워진 이진트리 ) 
데이터 삽입과 데이터 삭제의 시간복잡도는 O(logN)


✓ 우선순위 큐, Priority Queue
우선순위가 높은 데이터가 먼저 나가는 구조, 일반적인 큐와 달리 트리구조
완전 이진트리 형태의 힙을 이용해 구현, 시간 복잡도는 O(logN)으로 같다.

💡 우선순위 큐와 힙은 엄연히 말하면 다르다. 하지만 힙은 우선순위 큐를 구현할 수 있는 좋은 자료구조이다.

 
 
 
1. 반환할 결과값 count를 선언하고 최소힙 기능을 가지고 있는 heapq Module을 사용하여 스코빌 지수를 힙의 형태로 만들어줍니다.
 
 
2. 스코빌 지수가 1개 남을 때까지 while loop을 돌려줍니다.
 
 
3. '가장 맵지 않은 음식의 스코빌 지수'를 heappop 함수를 통해 꺼낸 뒤 first 변수에 담아줍니다.
 
 
4. first 변수에 담긴 값이 K 이상이면 종료합니다. 그렇지 않으면 5번으로 넘어갑니다.
 
 
5. 섞은 횟수를 1 증가시키고, '두 번째로 맵지 않은 음식의 스코빌 지수'를 꺼내 second 변수에 담아줍니다.
 
 
6. '특별한 방법으로 섞기'를 연산하고 다시 스코빌 지수에 힙의 형태로 담아줍니다. 이후 다시 3번으로 이동합니다.
 
 
 

제출 코드

import heapq
def solution(scoville, K):
    count = 0            # 반환 할 결과값, 섞은 횟수
    heapq.heapify(scoville) # 스코빌 지수 우선순위 큐
    
    # 스코빌 지수가 1개 남을 때까지 while loop
    while len(scoville) > 1:
        # '가장 맵지 않은 음식의 스코빌 지수'
        first = heapq.heappop(scoville)
        
        # '가장 맵지 않은 음식의 스코빌 지수'가 K보다 작다면
        if first < K:
            count += 1                                  # 섞은 횟수 1씩 증가
            second = heapq.heappop(scoville)               # '두 번째로 맵지 않은 음식의 스코빌 지수'
            heapq.heappush(scoville, (first + (second * 2))) # '특별한 방법으로 섞기' 후 다시 담기
        # 가장 맵지 않은 음식의 스코빌 지수'가 K 이상이면 종료
        else:
            break
        
    # '가장 맵지 않은 음식의 스코빌 지수'가 K보다 작으면 -1, 그렇지 않으면 while loop 섞은 횟수 반환
    return -1 if scoville[0] < K else count

 

 
 
 
 
 
 
 
 
 
 

---

 
 
 
 
 
 
 
 
 
 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges