[프로그래머스 LV.2] 더 맵게

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

전체 코드

from heapq import *
def solution(scoville, K):
    answer = 0
    heapify(scoville)
    while(scoville[0]<K):
        if len(scoville) < 2:
            return -1
        heappush(scoville,mixScov(heappop(scoville),heappop(scoville)))
        answer +=1
        
    return answer

def mixScov(first,second):
    return first+(second*2)

 

알고리즘 설명

heap queue를 사용하여서 문제를 해결하였다.

heap?

heap이란, 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조다. 여러 값들 중 최대/최솟값을 빠르게 찾아낼 수 있다.

이 문제에서는, min heap을 사용하였다.

min heap은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리이다.

min heap을 사용하면 원소들이 항상 정렬된 상태로 추가 및 삭제된다. 그리고, 가장 작은 값은 언제나 0번 인덱스에 위치한다.

 

Python의 heapq 모듈을 import 하여 heap 자료구조를 사용할 수 있다.

일반적인 list를 heap queue로 변환하기 위한 함수 : heapify(list_name)

heap에서 원소를 추가하기 위한 함수 : heappush(list_name, value)

heap에서 원소를 삭제하기 위한 함수 : heappop(list_name)

코드 설명

scoville 지수를 섞은 후, 결괏값이 최솟값보다 작은지, 큰지 알 수 없다. 따라서 내부적으로 정렬을 해 줄 수 있는 heap 자료구조를 사용하였다.

기존의 scoville List를 heap queue로 변환하였다. 기본적으로 Python에서 제공하는 heapq 모듈을 사용하면 min heap을 기준으로 기능을 제공한다. min heap에서 index 0번째가 최솟값이기 때문에, 최소값이 K 이상이 될 때까지 while문을 통해 while 문 내부의 코드를 반복한다.

만약, scoville heap queue의 길이가 2 미만이라면, item을 섞을 수 없기 때문에 -1을 return 한다. 왜냐하면 while문을 탈출하지 못했다는 것은 scoville heap queue 내부 요소의 최솟값이 K 미만이라는 뜻인데, 더 이상 item을 섞을 수 없는 상황이기 때문이다.

scoville heap queue의 길이가 2 이상이라면, 최솟값과 그다음 작은 값(heap queue에서 index 0,1번)을 섞어서 결괏값을 scoville heap queue에 push한다. push하게 되면, 내부적으로 정렬하여 결과값을 알맞은 자리에 위치시킨다. 그 후, answer를 1 증가시킨다.