[프로그래머스] 구명보트 - Python

이번에 해결해 볼 문제는 프로그래머스에 있는 구명보트이다.

---

문제 설명

• 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려 한다.
• 구명보트에는 최대 2명 탈 수 있으며 무게 제한도 있다.
• 사람들의 몸무게가 주어졌을 때 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 한다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.

문제 해결 아이디어

1. 문제를 읽고 나서 마땅히 방법이 떠오르지 않으면 Greedy Algorithm을 떠올려 볼 수 있다.
2. 또한 문제에서 하나의 보트에는 최대 2명, 무게 제한이라는 두 가지 제한사항과 함께 최대한 적게 사용이라는 문장을 통해 Greedy Algorithm 아닐까하는 생각을 할 수 있다.
3. Greedy Algorithm을 사용하기 위해서는 어떤 것을 탐욕적으로 선택할지 정해야 한다.
   • 우선 몸무게가 무거운 사람부터 구명보트에 태운다.
   • 태우고 남은 자리의 무게가 가장 큰 것을 다음 사람을 태울 때 먼저 고려한다. (Greedy)

문제 해결 코드

import heapq

def solution(people, limit):
    answer = 1
    people.sort(reverse=True)

    q = []
    heapq.heappush(q, (limit - people[0])*-1)

    for weight in people[1:]:
        # 남은 자리의 무게 중 가장 큰 것
        rest = q[0] * -1

        # 기존에 있던 구명보트에 태우기
        if rest >= weight:
            heapq.heappop(q)

        # 새로운 구명보트 추가
        else:
            # 남은 자리의 무게를 우선순위 큐에 저장
            heapq.heappush(q, (limit - weight)*-1)
            answer += 1

    return answer