알고리즘 풀이: [프로그래머스] 더 맵게

https://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 합니다.

 

입출력 예

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개를 구합니다. 최솟값 2개를 가지고 새로운 스코빌 지수를 연산하고 이를 다시 힙에 넣습니다. 이 과정을 반복하여서 최솟값이 K 보다 크게 합니다.

 

 

힙 자료구조는?

 

힙 자료구조는 기본적으로 (이진) 트리의 형태를 띄고 있습니다. 힙 자료구조의 가장 큰 특징은 부모가 자식보다 무조건 작다(크다)는 것입니다. 부모가 자식보다 무조건 작은 힙 자료구조를 최소 힙(min heap)이라 부릅니다. 최소 힙인 경우 루트에 최솟값이 저장됩니다. 결국 힙 자료구조를 사용해서 루트를 조회하면 최솟값을 빠르게 구할 수 있습니다.

 

힙 자료구조를 직접 구현할 수도 있지만 프로그래밍 언어마다 이를 구현한 내장 라이브러리가 있습니다. 파이썬에서도 heapq 내장 라이브러리를 통해서 리스트를 힙 자료구조로 사용할 수 있습니다. 힙에서 루트 값(최솟값)을 반환하는 heappop과 힙에 원소를 추가하는 heappush가 대표적인 함수입니다. 이러한 함수들은 힙 구조를 유지시킨 채 힙의 원소들을 관리합니다.

 

 

그래서 문제를 해결해봅시다.

 

우선 scoville 리스트를 힙 자료구조로 만들어야 합니다. 이는 앞서 살펴본 파이썬 내장 라이브러리 heapq를 사용합니다.

초기화 단계. scoville은 힙 자료구조로 변환된 상태

힙에서 원소를 pop 하고 push 하는 것을 조건에 따라 반복하고, 스코빌 지수를 섞는 횟수를 세어줍니다.

 

 

반복 1회 차

 

 

가장 작은 스코빌 지수 1과 2를 섞어서 스코빌 지수 5 생성

힙에서 가장 작은 스코빌 지수 값은 1입니다. 이는 하한선이 되는 K(=7) 보다 작으므로 그다음 작은 스코빌 지수(2)와 혼합하여서 스코빌 지수를 높여야 합니다. 연산(가장 덜 매운 스코빌 지수 + 2 * 그다음으로 매운 스코빌 지수)을 통해 새로운 스코빌 지수 5를 생성합니다. 그리고 이를 다시 힙에 원소로 넣어줍니다. 

 

 

반복 2회 차

가장 작은 스코빌 지수 3과 5를 섞어서 스코빌 지수 13 생성

가장 작은 스코빌 지수(3)가 하한선 K(7) 보다 작으므로 위의 과정을 스코빌 지수 3과 5에 대해서 반복합니다. 

 

 

반복 종료

 

반복 종료

 

가장 작은 스코빌 지수(9)가 하한선 K(7) 보다 큰 경우입니다. 따라서 더 이상 스코빌 지수를 섞는 것을 하지 않아도 됩니다. 최종 섞은 횟수 2를 반환합니다. 

 

소스 코드

메인 솔루션 함수

import heapq


def solution(scoville, K):
    # scoville을 힙 자료구조로 초기화
    heap = list()
    for s in scoville:
        heapq.heappush(heap, s)

    counter = 0

    # 가장 작은 스코빌 지수
    s1 = heapq.heappop(heap)
    while s1 < K:
        if not heap:
            return -1

        # 그 다음으로 작은 스코빌 지수
        s2 = heapq.heappop(heap)
        # 섞은 스코빌 지수
        s3 = s1 + 2 * s2
        counter += 1

        # 섞은 스코빌 지수를 다시 힙에 원소로 넣는다
        heapq.heappush(heap, s3)

        s1 = heapq.heappop(heap)

    return counter


if __name__ == '__main__':
    assert solution([1, 2, 3, 9, 10, 12], 7) == 2

프로그래머스 화면

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%EB%8D%94%20%EB%A7%B5%EA%B2%8C.py

dhsong95/-PRACTICE-Programmers-Algorithm