[LeetCode] 881. Boats to Save People - Java

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

Boats to Save People - LeetCode

---

문제

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 * 104
• 1 <= people[i] <= limit <= 3 * 104

---

풀이

풀이 과정

사람들의 몸무게가 담긴 배열 people과 보트에 한번에 탈 수 있는 최대 무게 limit가 주어질 때 모든 사람이 타기위해 필요한 보트의 최소 개수를 구하는 문제이다.
보트에는 동시에 두 사람까지 탑승할 수 있다.

가장 적은 보트를 사용하기 위해서는 사람들을 몸무게 순으로 정렬하여 몸무게가 많이 나가는 사람이 탑승할 때 가능한 경우 가벼운 사람이 함께 탑승하는 것이 가장 효율적이다.
따라서 사람들을 먼저 무게순으로 정렬하고 양쪽끝에서 부터 비교를 하도록한다.

int answer = 0;
        
// 사람들을 무게순으로 정렬
Arrays.sort(people);

// 왼쪽 인덱스
int left = 0;
// 오른쪽 인덱스
int right = people.length - 1;

 

왼쪽 인덱스와 오른쪽 인덱스가 교차할 때 까지 반복하며 탐색할 때마다 보트의 수를 하나씩 증가시키고
오른쪽 사람의 무게와 왼쪽 사람의 무게 합이 limit 이하인 경우 양쪽 인덱스를 모두 안쪽으로 한 칸씩 이동,
오른쪽 사람의 무게와 왼쪽 사람의 무게 합이 limit 초과하는 경우 오른쪽 인덱스만 이동한다.
왼쪽과 오른쪽 인덱스가 같은 경우에는 남은 사람이 한 사람이므로 보트 개수를 증가시키고 탐색을 바로 종료한다.

// 왼쪽과 오른쪽 인덱스가 교차할 때까지 반복
while(left <= right) {
    answer++;

    // 왼쪽과 오른쪽 인덱스가 같은 경우 탐색 종료
    if(left == right) break;

    // 오른쪽 사람의 무게와 왼쪽 사람의 무게 합이 limit 이하인 경우 양쪽인덱스를 모두 이동
    if(people[right] + people[left] <= limit) {
        right--;
        left++;
    }
    // 오른쪽 사람의 무게와 왼쪽 사람의 무게 합이 limit 초과하는 경우 오른쪽 인덱스만 이동
    else right--;;
}

 

최종적으로 구해진 보트의 개수를 return 한다.

return answer;

---

최종 코드

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int answer = 0;
        
        // 사람들을 무게순으로 정렬
        Arrays.sort(people);
        
        // 왼쪽 인덱스
        int left = 0;
        // 오른쪽 인덱스
        int right = people.length - 1;
        
        // 왼쪽과 오른쪽 인덱스가 교차할 때까지 반복
        while(left <= right) {
            answer++;
            
            // 왼쪽과 오른쪽 인덱스가 같은 경우 탐색 종료
            if(left == right) break;
            
            // 오른쪽 사람의 무게와 왼쪽 사람의 무게 합이 limit 이하인 경우 양쪽인덱스를 모두 이동
            if(people[right] + people[left] <= limit) {
                right--;
                left++;
            }
            // 오른쪽 사람의 무게와 왼쪽 사람의 무게 합이 limit 초과하는 경우 오른쪽 인덱스만 이동
            else right--;;
        }

        return answer;
    }
}

---