Heap - 더 맵게(Lv.2)

문제 설명

매운 것을 좋아하는 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. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

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

 

 <My Source Code 1>

#스코빌 지수 K 이상인지 확인 
def chkK(sortedScoville, K):
    for i in range(len(sortedScoville)):
        if sortedScoville[i] < K:
            return False
        else:
            return True

#스코빌 지수 K 미만이 존재하는 경우 재귀함수로 반복해서 제거
def recurFuc(scoville, K, answer):
    TFchkK = chkK(scoville, K)
    if TFchkK == True:
        return answer
    elif TFchkK == False:
        firScov = scoville.pop(0)
        secScov = scoville.pop(0)
        scoville.append(firScov + (2*secScov))
        answer += 1
        return recurFuc(scoville, K, answer)
        
# main 함수
def solution(scoville, K):
    scoville.sort()
    answer = 0
    result = recurFuc(scoville, K, answer)
    return result

 처음에 이렇게 제출을했는데 아주 다양한 결과가 나왔다.

이유를 찾아보니 

1. "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다." 라는 조건 무시

2. recurFuc에서 scoville.sort()를 해주지 않음

 

이 2가지였다. 

그래서 이 두가지를 충족시킨 후 실행을 해봤다.

<My Source Code 2>

def chkK(sortedScoville, K):
    for i in range(len(sortedScoville)):
        if sortedScoville[i] < K:
            return False
        else:
            return True
        
def recurFuc(scoville, K, answer):
	# 추가2 : 정렬후, 최소값 + (두번째 최소값*2)
    scoville.sort()
    TFchkK = chkK(scoville, K)
    if TFchkK == True:
        return answer
    # 추가1 : K 이상의 스코빌 지수가 없는 경우 -1 return
    elif len(scoville) == 1:
        return -1
    elif TFchkK == False:
        firScov = scoville.pop(0)
        secScov = scoville.pop(0)
        scoville.append(firScov + (2*secScov))
        answer += 1
        return recurFuc(scoville, K, answer)
        
def solution(scoville, K):
    answer = 0
    result = recurFuc(scoville, K, answer)
    return result

결과는 정확성은 만점이나, 효율성에서 0점

 

 

 

 

 

 

 

 

 

 

나의 경우 재귀함수를 이용해 문제를 해결하였다.

그런데 보통 재귀함수는 효율성면에서 꽝이라고 한다... 알고는 있었지만 이 문제에서 생각나는것 이것 뿐이었다...

다시 고민을 해봤다.

 

재귀함수를 이용하지 않고 사용하니 비교적 단순해졌다. 그렇지만 한번에 통과할 일은 절대 없지...

테스트16 넌 뭐냐... 효율성 테스트는 바라지도 않고, 실행결과라도 잘 나오면 어떻게든 다듬어 보겠는데... ㅠ.ㅠ

그런데 !!!! 테스트 16은 solution의 if문(K 이상의 값이 없는 경우 -1 반환하는 조건문)의 위치를 변경해주니 패스되었다.

실행순서의 중요성을 다시한번 체감했다...

 

<My Source Code 3>

def chkK(sortedScoville, K):
    sortedScoville.sort()
    for i in range(len(sortedScoville)):
        if sortedScoville[i] <= K:
            return True
        else:
            return False
        
def solution(scoville, K):
    
    cnt = 0
    while chkK(scoville, K):
    	#변경후
    	if len(scoville) == 1:
            cnt = -1
            break
        scoville.sort()
        cnt+=1
        firScov = scoville.pop(0)
        secScov = scoville.pop(0)
        scoville.append(firScov+(2*secScov))
        #변경전
        #if len(scoville) == 1:
        #    cnt = -1
        #    break
    return cnt

 

이제 남은건 효율성이다...

 

효율성의 문제를 해결하기 위해서는 힙을 써야했다... Heapq 라이브러리를 사용했어야한다는 말씀

이걸 사용하니 단번에 문제가 해결됐다...

<My Source Code 4>

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    cnt = 0
    while scoville[0] < K:
        if len(scoville) == 1:
            cnt = -1
            break
        cnt+=1
        firScov = heapq.heappop(scoville)
        secScov = heapq.heappop(scoville)
        heapq.heappush(scoville, (firScov+(2*secScov)))

    return cnt

Heap
각 노드의 key 값이 자식노드의 key 값보다 작지 않거나 크지 않은 완전 이진 트리

* Heap 구조는 최대, 최솟값을 계속해서 호출해야 하는 상황인 경우에 사용하면 시간측면에서 효율적인 구현이 가능하다. *