[코테] 99클럽 코테 스터디 5일차 TIL - 힙

 

Question1 - [미들러] 더 맵게

 

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42626

 

매운 것을 좋아하는 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 합니다

•  

---

 

문제풀이 

 

trial1  

정확도는 통과했으나 효율성 통과 못해서 다시 풀어야 했음.

우선 첫번째 시도로 푼 방법은, 리스트 및 정렬의 성질을 활용해서 푼 것으로,

scoville에 1개 이상의 원소가 있는 한 계속 섞기를 반복하고, 모든 scoville이 K 이상이라면 우선 반환한다.

또한 scoville 이 K가 넘는지를 확인하는 check_scoville 함수와 solution을 구분해서 solution의 return 부분에서 함수를 활용하도록 했다. 풀긴 했다지만 매우 비효율적. 

def check_scoville(scoville, K):
    for i in scoville:
        if i < K:
            return False
    return True

def solution(scoville, K):
    mix_count = 0
    
    while len(scoville) > 1:
        scoville.sort()  # 정렬
        if scoville[0] >= K:
            return mix_count
        
        new_scoville = scoville[0] + scoville[1] * 2
        scoville = scoville[2:]  
        scoville.append(new_scoville)  
        mix_count += 1
    
    return mix_count if check_scoville(scoville, K) else -1

 

 

*** heap 개념

 

문제를 풀기 위해 heap 부터 알아보자.

heap 개념은 힙은 완전 이진 트리 형태로 요소가 저장되며,

Max heap은 상위 노드가 하위 노드보다 무조건 큰, Min heap은 상위 노드가 하위 노드보다 무조건 작은 자료구조이다.

 

파이썬에 heapq 모듈을 활용해 힙을 구현할 수 있으며, 사용 예제는 아래와 같다. 

heap.heapify를 하면 리스트가 작은 순서대로 정렬,

heap.heappop을 하면 가장 작은 요소를 꺼내게 된다.

여기서 중요한 점은, heap.heappush를 해서 힙을 만들때, 자동 정렬된다는 점이다.

 

import heapq

# 빈 리스트를 힙으로 사용
heap = []

# 요소 추가
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 9)
heapq.heappush(heap, 2)
heapq.heappush(heap, 6)

# 힙에서 요소를 꺼내기 (가장 작은 요소)
print(heapq.heappop(heap))  # 출력: 1
print(heapq.heappop(heap))  # 출력: 1
print(heapq.heappop(heap))  # 출력: 2

# 힙 상태 출력
print(heap)  # 출력: [3, 4, 5, 6, 9]

# 리스트를 힙으로 변환
lst = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(lst)

# 힙 상태 출력
print(lst)  # 출력: [1, 1, 2, 3, 5, 9, 4, 6]

# 힙에서 가장 작은 요소를 꺼내기
print(heapq.heappop(lst))  # 출력: 1

 

heapq 모듈은 기본적으로 최소 힙만을 지원한다.

따라서 최대 힙을 구현하려면 아래 처럼, 부호를 반전하여 최소 힙에 요소를 추가하고 추출할 때 다시 부호를 반전하여 최대힙을 구현해야 한다. 

import heapq

# 빈 리스트를 힙으로 사용
max_heap = []

# 최대 힙에 요소 추가
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)

# 최대 힙에서 가장 큰 요소 추출 (절대값이 가장 큰 값)
max_value = -heapq.heappop(max_heap)
print(max_value)  # 출력: 5

 

 

trial 2 : heap 개념 사용 ★

 

이제 heapq 를 이용해서 최소힙을 이용해 문제를 다시 풀어보자. 

먼저 heap으로 scoville을 작은 수부터 정렬 해준 뒤에. scoville[0] >= K라면 return 하는 함수는 그대로 

heap에서 작은 요소부터 두번을 pop한 뒤에 mixture의 값을 heap에 다시 추가해준다.

 

여기서 중요한, heap이 효율적인 이유는 heapq.heappush() 함수를 사용하여 요소를 힙에 추가하면 자동으로 정렬된다는 특성 때문이다.

따로 정렬 로직을 주지 않고도, mixture마다 추가하면 정렬이 자동으로 된다.

마지막으로 자동 정렬된 scoville의 첫번째 가장 작은 요소의 값이 K이상인지만 확인하면 된다.! 

 

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)  # heap으로 만들기 (작은수부터 정렬) 
    count = 0
    
    while len(scoville) > 1 :
        if scoville[0] >= K:  
            return count
        
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)

        new = a + 2*b
        heapq.heappush(scoville, new)
        
        count += 1  
    
    return count if scoville[0] >= K else -1

 

---

Question2 - [챌린저] 디스크 컨트롤러

 

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/42627)