[프로그래머스 스터디] 더 맵게 - Python

문제

프로그래머스 더 맵게

풀이

import heapq

def solution(scoville, K):
    mixCnt = 0
    heapq.heapify(scoville)

    while scoville[0] < K:
        mixed = heapq.heappop(scoville) + 2 * heapq.heappop(scoville)
        heapq.heappush(scoville, mixed)
        mixCnt += 1

        # 더이상 섞을 것이 없고 마지막 남은 것이 여전히 K보다 작다면 불가능으로 판단
        if len(scoville) == 1 and scoville[0] < K:
            return -1

    return mixCnt

요약

스코빌 지수가 가장 낮은 것과 두번째로 낮은 것을 섞어 새로운 것을 만들어 넣고 모든 음식의 스코빌 지수를 K이상으로 만들어야 하는 문제.
가장 낮은 수를 가진 음식, 그리고 두번째로 낮은 수를 가진 음식 두가지 모두 필요하고 새로운 수를 넣을때 마다 재정렬이 필요하다 생각해서 heap을 이용하면 편하겠다고 생각함.

  1. scoville 리스트를 heapify로 heap으로 바꿔주고 scoville의 root( 파이썬의 heap은 최소힙으로 구현되있기 때문에 root은 가장 작은 값 )을 두차례 뽑는다.
    그 후 주어진 계산식에 따라 섞어 만든 새로운 음식(mixed)를 만들고, 그때마다 mixCnt를 1씩 증가
  2. 예외 상황 : 더이상 섞을 것이 없고 또한, 마지막 남은 것이 여전히 K보다 작다면 불가능

피드백을 받고 개선된 풀이

기존코드

while scoville[0] < K:
        mixed = heapq.heappop(scoville) + 2 * heapq.heappop(scoville)
        heapq.heappush(scoville, mixed)
        mixCnt += 1

        # 더이상 섞을 것이 없고 마지막 남은 것이 여전히 K보다 작다면 불가능으로 판단
        if len(scoville) == 1 and scoville[0] < K:
            return -1

개선된 코드

    while scoville[0] < K:
        try:
            mixed = heapq.heappop(scoville) + 2 * heapq.heappop(scoville)
            heapq.heappush(scoville, mixed)
            mix_cnt += 1
        except:
            return -1
  • 기존의 heappop()을 진행할시에 아무것도 없는 빈 heap에서 pop할때 발생되는 IndexError를 if문을 통해 처리했었는데 try-except문을 통해 더욱 더 깔끔하고 파이써닉하게 수정,개선시킬 수 있었다.

...

마지막 하나인 상황만 생각하고 마지막 하나가 K보다 클때는 고려하지못한채 -1을 return해 처음에 계속 틀렸었다.

좋은 웹페이지 즐겨찾기