[Algorithm] [Python] Programmers - 더 맵게

Programmers - 더 맵게

문제 설명

---

매운 것을 좋아하는 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 합니다.

 

제출 코드

---

1차 제출 코드

def solution(scoville, K):
    cnt = 0
    while min(scoville) < K:
        cnt += 1
        scoville.sort(reverse=True)
        minimum = scoville.pop()
        next_minimum = scoville.pop()
        scoville.append(minimum + next_minimum*2)
    return cnt

정확성 몇몇 케이스와 효율성 전체에서 무너졌다.

 

그렇다, 최악의 경우 sort를 n번 진행하게 되므로 시간복잡도가 꽝이다.

 

또한, 제한 사항 중 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다. 라는 사항을 놓쳤다.

 

2차 제출 코드

def solution(scoville, K):
    cnt = 0
    while min(scoville) < K:
        cnt += 1
        scoville.sort(reverse=True)
        try:
            minimum = scoville.pop()
            next_minimum = scoville.pop()
            scoville.append(minimum + next_minimum*2)
        except IndexError:
            return -1
    return cnt

남아있는 원소가 없어서 인덱스 에러가 발생할 경우, -1을 리턴한다.

 

위 코드의 경우에는 정확성 테스트는 모두 만족한다.

 

다만, 효율성 테스트에서 완전히 무너졌다.

 

최종 제출 코드

def solution(scoville, K):
    import heapq
    cnt = 0
    heapq.heapify(scoville)      # heap 자료구조로 변환

    while scoville[0] < K:       # 최소값이 K보다 작다면 반복한다.
        try:
            heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)         # 최소값 + 다음 최소값 * 2 를 heap에 push
            cnt += 1
        except IndexError:       # indexError 발생시 -1 반환
            return -1
    return cnt

 

문제풀이

---

리스트를 이용한 문제풀이는 정확성은 모두 만족하였으나 반복을 진행할 때 마다 sort를 진행하기 때문에 효율성에서 통과하지 못했다.

 

sort 내장함수를 사용하지 않고 최소값을 알아낼 수 있는 방법이 무엇이 있을까 고민하다가 heap 자료구조를 생각하게 되었다.

 

파이썬에서 heapq 모듈을 이용하여 힙을 편하게 구현할 수 있었으며 이를 통해 문제를 풀어낼 수 있었다. (오늘 처음써봤는 역시 파이썬...)

 

전달받은 리스트를 heapq.heapify() 을 통해 heap구조로 변환한다.

 

파이썬의 heapq는 기본적으로 MinHeap 구조를 따르기 때문에 heapq[0]에는 배열 내 최소값이 위치하게 된다.

 

따라서, heapq.heappop(scoville) + heapq.heappop(scoville) * 2 연산을 통해 스코빌 지수를 구하고 이를 heapq.heappush() 함수를 이용하여 heap 내에 넣어준다.