99클럽 코테 스터디 16일차 TIL + 자료구조, 힙, heapq, heapq.heaptify(), heappop(), heappush()

임정민·2025년 2월 10일

[99클럽5기] - 1일 1코테

목록 보기

16/26

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인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.

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

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

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

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

2. 풀이

import heapq

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

    while len(scoville) > 1:

        first = heapq.heappop(scoville)
        if first >= K:  
            return mix_count

        second = heapq.heappop(scoville)
        new_scoville = first + (second * 2)
        heapq.heappush(scoville, new_scoville) 
        mix_count += 1

    return mix_count if scoville[0] >= K else -1

3. 회고

3-1. 문제 해결 과정

힙으로 풀었어야 했는데 그냥 냅다 리스트로 풀었다. 근데 리스트로 풀면 비효율적이기도 하고 계속 정렬을 해야하기 때문에 차라리 힙으로 푸는게 훨 더 낫다.

먼저 heapq.heapify(scoville)과 mix_count = 0를 작성하여 최소 힙과 섞은 횟수를 알 수 있는 변수를 선언했다. 이후에는 스코빌 지수의 배열이 2 이상일 때부터 while 문이 돌아갈 수 있도록 했다.

heapq.heappop(scoville)을 통해 가장 작은 값을 추출하여 최소 값이 이미 K 이상이면 mix_count를 바로 리턴하고, heapq.heapop(Scoville)을 다시 불러와서 두 번째로 작은 값을 가져와서 섞은 음식의 스코빌 지수를 계산한다.

그리고 heapq.heappush(scoville, new_scoville)을 통해 새로운 스코빌 지수를 힙에 삽입한다. 반복이 종료된 후에는 마지막 값이 K 이상인지 확인하고 조건을 만족하면 mix_count을 리턴하고 그렇지 않으면 -1을 리턴한다.

def solution(scoville, K):
    scoville.sort()  # 초기 정렬
    mix_count = 0  # 섞은 횟수

    while len(scoville) > 1:
        # 가장 작은 두 개의 값을 꺼냄
        first = scoville.pop(0)
        if first >= K:
            return mix_count  # 모든 음식이 K 이상이면 종료

        second = scoville.pop(0)
        new_scoville = first + (second * 2)
        
        # 새로운 값을 올바른 위치에 삽입하기 위해 정렬
        scoville.append(new_scoville)
        scoville.sort()
        
        mix_count += 1

    return mix_count if scoville[0] >= K else -1  # 마지막 값이 K 이상인지 확인

리스트만으로 구현한 코드도 있는데 확실히 귀찮은 부분이 많이 보인다. 해당 코드를 실행했으면 시간 초과가 나지 않았을까 생각도 들었다. 참고용으로 같이 첨부했다.

3-2. 새롭게 배운 내용

힙(Heap) : 우선순위 큐를 구현하는 데 사용되는 완전 이진 트리 자료 구조이다. 최소 힙(부모 노드의 값이 자식 노드보다 항상 작거나 같은 형태), 최대 힙(부모 노드의 값이 자식 노드보다 항상 크거나 같은 형태)로 나뉘는데 파이썬의 heapq 모듈은 최소 힙으로 동작한다. 그러므로 heapq를 사용한다면 가장 작은 값을 빠르게 찾을 수 있다.
heapq.heaptify() : 괄호 안의 리스트를 최소 힙으로 변환하여 가장 작은 원소가 항상 인덱스 0에 위치하게 된다.