[LeetCode] 881. Boats to Save People - 문제풀이

Description

각각 사람과 몸무게를 나타내는 배열이 있고 한 보토당 최대 옮길 수 있는 limit 무게 값이 주어졌을때 주어진 모든 사람을 태울 수 있는 최소 보트 수를  반환하는 문제입니다. 보트에는 근데 두명만 탈수 있음!!

You are given an array people where people[i] is the weight of the ith 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.

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Constraints:

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

Solution 1. Greedy (Two Pointer)

public static int numRescueBoats(int[] people, int limit) {
    int len = people.length;
    Arrays.sort(people);
    int start = 0;
    int end = len-1;
    int cnt = 0;
    while(start <= end){
        if(people[start] + people[end--] <= limit){ // 한명 더 태움
            start++;
        }
        cnt++;
    }
    return cnt;
}

배열을 정렬한 뒤에 가장 무거운 사람(end—)을 먼저 태우고 같이 갈 수 있는 가벼운 사람이 있다면 (≤limit) 한명을 더 태워서 (start++) 두포인터가 만날때 까지 반복해줍니다.

Reference

Boats to Save People - LeetCode