[프로그래머스 힙]더 맵게 - Python3

문제

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

코딩테스트 연습 - 더 맵게 | 프로그래머스

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 1 이상 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

알고리즘

def solution(scovile, k):
    import heapq
    answer = 0
    heap = []
    
    # 입력을 받은 scovile배열을 힙 자료구조인 heap에 넣어준다. 
    for i in range(len(scovile)):
        heapq.heappush(heap, scovile[i])

    while True:
        # heap에 원소가 더이상 없다면, -1을 리턴한다
        if len(heap) == 0:
            return -1

        # heap에 원소가 1개밖에 없다면, 2개의 원소를 pop할 수가 없다. 
        # 따라서, 하나의 값을 가지고 k보다 높은지 낮은지를 판단해서 결과를 리턴한다.
        if len(heap) == 1:
            # heap에 남아있는 유일한 원소의 값이 k보다 작다면, 더 이상 맵게 만들 수 없다. 따라서 -1을 리턴한다.
            if heap[0] < k:
                return -1
            # heap에 남아있는 유일한 원소의 값이 k보다 크다면, 조건을 만족한 것이므로 answer를 리턴한다
            else:
                return answer
        
        # 본 문제에서 사용한 힙은 최소 힙이다. 따라서, 0번째에는 값이 가장 작은 원소가 들어가있다. 
        # 이 값이 k보다 크다면, 다른 원소들 또한 k보다 큰 것이므로, answer를 리턴한다.
        if heap[0] >= k:
            return answer

        # 그렇지 않고 아직 heap에서 k보다 작은 원소가 있다면, heap에서 원소 2개를 꺼내서 temp1, temp2에 저장한다
        # 그리고 새로운 scovile 값을 만들어서, heap에 푸시한다.
        else:
            answer += 1
            temp1 = heapq.heappop(heap)
            temp2 = heapq.heappop(heap)
            new_scovile = temp1 + 2 * temp2
            heapq.heappush(heap, new_scovile)


scovile = [12, 10, 9, 3, 2, 1]
k = 7
print(solution2(scovile, k))

설명

문제를 해결하기 위해 힙을 사용할 것이다. 힙을 사용하고자 headq 라이브러리를 import한다. 그리고, scovile배열의 원소를 heap에 push한다. heap은 우선순위 큐이기 때문에, 힙에서 나온 값은 그 배열에서 가장 작은 값이다. 따라서, 배열을 계속 정렬해줄 필요가 없다. 

반복을 돌리면서, 다음의 제약사항에 주의한다.

• 배열에 원소가 없는 경우: 이 경우, 원소 2개를 pop하면 오류가 난다. 그러므로 -1을 리턴한다
• 배열에 원소가 1개만 남은 경우: 이 경우 또한 오류가 난다. 따라서, 그 하나의 값을 k와 비교해서, k보다 크다면 조건이 만족된 것으로 보고 answer를 리턴하고, 그렇지 않다면 원하는 답을 얻을 수 없다는 것으로 보고 -1을 리턴한다.
• 힙 자료구조의 특성상, heap[0]에는 가장 작은 원소가 들어가있다. 따라서, 이 값이 기준값k보다 크다면, 다른 원소들 또한 k보다 크다 할 수 있다. 따라서 heap[0] >= k라면, 반복을 중단하고 answer를 리턴한다

위 경우가 아니라면, 반복을 진행한다. answer의 값을 1 증가시키고, heap에서 원소 2개를 pop해서 가장 작은 2개의 원소를 저장한다. 그렇게 새로운 스코빌 값을 만들고, heap에 push한다. 

 

결과

올바른 결과를 출력한다

후기

힙으로 문제를 푼건 처음이었는데, 정렬해서 푸는것보단 확실히 좋다. 왜냐하면 처음에 내가 짰던 코드는, 최소값을 꺼내기 위해 반복을 돌면서 sort()를 했다. 그러면 시간복잡도가 엄청 늘어난다. sort()를 몇번이나 하게 되고, 제약 사항에 보면 scovile배열의 원소의 갯수가 최대 1000000개이다. 애초에 이렇게 풀면 안 된다는 걸 알았지만 내 눈으로 차이를 보고싶어서 위 방식으로 풀었는데, 그 코드는 다음과 같다. 

def solution(scovile, k):
    answer = 0
    scovile.sort(reverse=True)

    if len(scovile) == 0:
        return -1

    while True:
        if len(scovile) < 2:
            temp = scovile.pop()
            if temp < k:
                return -1
            else:
                return answer

        if check_arr(scovile, k) == 1:
            return answer

        else:
            print("다시 반복")
            answer += 1
            new_scovile = scovile[-1] + 2 * scovile[-2]
            scovile.pop()
            scovile.pop()
            scovile.append(new_scovile)
            scovile.sort(reverse=True)

뭐 자세히 볼건 전혀 없고, 그냥 배열에서 값 하나 뽑았으면 배열을 계속 정렬하는 것이 포인트다. 이렇게 해서 제출했더니, 정확성 테스트는 다 맞는데 효율성 테스트를 하나도 통과하지 못하더라. 그래서 힙을 사용해서 풀었는데, 너무도 다행히 정확성과 효율성을 통과했다. 힙을 쓰면 불필요한 정렬을 안해도 되어서 그런것 같다(정렬은 배열의 크기가 커질수록 시간을 많이 잡아먹는다).

다음부터 굳이 정렬을 할 필요 없이, 최대값이나 최소값을 뽑아서 문제를 풀어야 할 일이 생긴다면 꼭 힙을 쓰도록 해야겠다. 원래는 힙에 대한 정리도 하려고 했는데, 지금 딴 문제가 넘넘 어려워서 그거 풀어야된다. 공부를 더 해야하긴 하니까 힙에 대해서는 나중에 올리겠다.