[2024] day 126. Leetcode 881. Boats to Save People

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 4일 (토)
Leetcode daily problem

881. Boats to Save People

https://leetcode.com/problems/boats-to-save-people/?envType=daily-question&envId=2024-05-04

Problem

people[i]가 i번째 사람의 무게인 people 배열과 각 보트가 한계의 최대 무게를 운반할 수 있는 무한한 수의 보트가 제공된다.
각 보트에는 동시에 최대 2명의 사람이 탑승할 수 있다.
단, 해당 인원의 무게 합계가 최대 한도여야 한다.
주어진 모든 사람을 태울 수 있는 최소 보트 수를 반환한다.

Solution

greedy algorithm (그리디 알고리즘)

그리디 알고리즘을 사용해서 무거운 사람과 가벼운 사람을 함께 태우려고 해, 한 보트에 최대한 많은 사람을 태우는 것이 핵심이다.
먼저 사람을 무게 순으로 절열하고, 두 사람을 같이 태울 수 있는지 판단해 보트의 수를 최소화 한다.

Code

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        l,r = 0, len(people)-1
        boat = 0
        
        while l<=r:
            if people[l] + people[r] <= limit:
                l+=1
            
            r-=1
            boat+=1
        
        return boat
                

Complexicity

시간 복잡도

people 배열을 정렬할 때 O(nlogn)의 시간이 소요되고,
while 루프에서 이중 포인터를 사용해 순환하므로 O(n/2)이 소요된다.
그래서 전체 시간 복잡도는 O(nlogn)이다.

공간 복잡도

추가적인 배열이나 자료구조를 사용하지 않으므로 입력으로 주어진 배열을 저렬하는데 필요한 공간만 사용한다. 따라서 공간복잡도는 O(1)이다.