Heap - 매운음식 성애자(Way Cool)

프로그래머스의 힙의 첫번째 문제입니다. 

programmers.co.kr/learn/courses/30/lessons/42626?language=python3

코딩테스트 연습 - 더 맵게

 

문제는 굉장히 간단합니다.

 

매운음식을 굉장히 사랑하는 매운음식 성애자가 있고,

 

모든 음식의 매운 정도가 스코빌 지수라는 값으로 있다고 가정합니다.

 

이때 가장 안매운 음식이 K이상의 스코빌 지수가 되길 원하는 상태입니다.

 

만약 안매운 음식이 K이하의 스코빌을 갖는다면

 

Mix음식 = 가장 안매운 음식의 스코빌 + 2번째로 안매운 음식의 스코빌*2

 

의 Mix 음식으로 재탄생 되게 됩니다.

 

알고리즘은 간단합니다.

1. 요리의 Min값을 도출한다.

2. 해당 요리의 스코빌을 K와 비교한다.

2_1 K보다 크면 알고리즘 종료

3. K보다 작으면 Min값을 한번더 도출

4. Mix음식을 생성 후 요리 List에 Add

5. 1~4반복

 

위 방법을 일반적인 정렬 알고리즘으로 가능합니다.

 

하지만 정렬 알고리즘은 최소 nlogn(Count기반 정렬 제외)의 시간복잡도를 보여주기 때문에

 

해당 문제를 Sort로 해결하는 것은 매우 비효율적인 상황이 됩니다.

 

이때 Cool Way(쉬운길)로는 Python의 List의 Min, Pop을 사용하는 방법이 있습니다.

def solution(scoville, K):    
    #가장 안매운 음식의 스코빌이 K이상일때까지 Mix횟수
    answer = 0
    init_len = len(scoville)
    #가장 안매운 음식의 스코빌이 K상이거나, 남은 음식이 하나일경우 알고리즘 종료
    #하나인경우 종료하는 이유는 이전에 Mix된 음식의 스코빌이 K이하인것을 확인하고
    #다시 List에 들어온 음식이기 때문입니다.
    while min(scoville)<K and len(scoville)!=1:        
    	#가장 안매운 + 2번째로 안매운 음식의 스코빌을 추출하여
        #Mix음식을 만들고, Mix 음식의 스코빌을 다시 음식 List에 넣습니다
        scoville.append(scoville.pop(scoville.index(min(scoville)))+scoville.pop(scoville.index(min(scoville)))*2)
        answer += 1  
    #while 문 내의 반복문을 줄이기 위한 방법이며
    #반복문 완료 후에도 가장 안매운 음식이 K이하이면
    #목표에 도달하지 못한 것이므로, Answer를 -1로 치환함
    if min(scoville)<K:
        answer = -1
    
    return answer

 

하지만 위 방법을 사용할 경우 효율성에서 시간 초과로 통과가 불가능합니다.

 

이때 Heap을 사용하면 빠른 답을 찾을수있을 것이란것을 알 수 있습니다.

 

Heap같은 경우 Max or Min값을 찾고 다시 List를 정렬하는데 logn의 시간복잡도를 보여줍니다.

teus-kiwiee.tistory.com/18?category=913859

Heap Sort

Min, Max 모두 n의 시간복잡도를 보인다는것을 생각하면,

 

Heap을 사용하면 빠른 시간안에 결과를 도출할 수 있을것으로 예상됩니다.

 

teus-kiwiee.tistory.com/85

매운음식 성애자(Way Cruel)