[python3] 881. Boats to Save People

풀이 일자: 23.04.03

난이도: [Medium]

분류: [Array, Two Pointers, Greedy, Sorting]

문제 내용

사람들의 무게가 담긴 people이라는 배열이 주어졌을 때 최대중량이 limit인 배를 이용해 최대 2명의 사람들을 운반하고자 한다면 최소 몇 개의 배가 필요한지에 대한 문제였다.

 

문제 해결 흐름 

1. 제일 먼저 떠올릴 수 있는 건 Greedy가 제일 먼저 떠오르겠다.

→ 최소한으로 옮겨야 하므로 Greedy하게 무게가 제일 많이 나가는 애랑 적게 나가는 애랑 같이 운반할 수 있다면 최소가 되겠네

 

2. 무게의 순서가 중요하니까 people에 대한 sort는 필수적이다.

→ sort를 해서 시작점과 끝점에 포인터를 두고 가장 무게가 큰 것부터 시작해서 되도록 맨 앞에 있는 사람까지 포함할 수 있도록 해야 한다.

 

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

        while(i <= j):
            weight = people[j];
            j -= 1;
            if (weight + people[i] <= limit):
                i += 1;
            boats += 1;

        return boats;

Time Complexity:  O(NLogN)

Python의 sorting algorithm이 NLogN의 시간복잡도를 가지고 있어 이게 시간 복잡도가 될 것이다.

 

Space Complexity: O(1)

새로 선언한 변수외에 다른 자료구조를 사용하지 않았기 때문에 공간 복잡도는 1이다..

 

다른 해결 방식

Ofiicial Solution과 다른 사람의 풀이에서 나와 같은 방식으로 Two pointer를 이용한 greedy문제로 풀었음을 확인할 수 있었다.

 

문제 링크

https://leetcode.com/problems/boats-to-save-people/description/

Boats to Save People - LeetCode