- Problem

881. Boats to Save People

지문 중에 중요한 것은 보트는 최대 2명만 태울 수 있다라는 점이다.

- 내 풀이

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        left, right = 0, len(people) - 1
        boats = 0

        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1
                right -= 1
            else:
                right -= 1
            boats += 1

        return boats

정렬과 투 포인터를 이용하여 해결했다.

우선, 사람들을 무게 순으로 정렬한다.
첫 사람과 끝 사람(가장 가벼운 사람과 가장 무거운 사람)이 한 보트에 탑승 가능하다면 같이 태운다.
그렇지 않다면, 가장 무거운 사람 혼자 보트에 태운다.
이 과정을 반복하며 그리디하게 접근한다.

- 결과

• 시간 복잡도: O(NlogN)
• 공간 복잡도: O(1)