[LeetCode] 881 | Boats to Save People | Python

---

문제 링크: https://leetcode.com/problems/boats-to-save-people/

---

문제

You are given an array people where people[i] is the weight of the $i^{th}$ person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

---

조건

• 1 <= people.length <= 5 * $10^4$
• 1 <= people[i] <= limit <= 3 * $10^4$

---

내 풀이

한 보트에 최대 두명이 들어갈 수 있다는 점을 염두에 둔다.

people을 정렬한 후, 제일 무거운 사람(people[n])을 보트에 넣은 뒤, 제일 가벼운 사람(people[front])을 넣어도 무게 제한에 걸리지 않는지 확인한다.

가벼운 사람은 front라는 인덱스로 앞에서부터 뒤로 나아가며, front와 n이 만난다면 그 사람까지 태워야하므로 ans+=1을 진행하고, front와 n이 지나간다면(ex. 총 사람이 3명일 때, n: 3 $\rightarrow$ 2 $\rightarrow$ 1, front: 0 $\rightarrow$ 1 $\rightarrow$ 2일 때) 모든 사람을 태운 것이므로 그냥 break한다.

---

코드

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people = sorted(people)
        N = len(people)
        ans = 0
        
        front = 0
        for n in range(N-1, -1, -1):
            if front > n:  break
            elif front == n:
                ans += 1
                break
            if people[n] + people[front] <= limit:
                front += 1
            ans += 1
        
        return ans