LeetCode 881. Boats to Save People

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

Boats to Save People - LeetCode

 

문제 요약

 

1. 사람들이 타기 위한 보트의 최소 갯수를 구합니다.

2. 보트 1대 당 최대 중량 limit 이하의 무게만 탑승이 가능합니다.

3. 보트 1대 당 최대 인원 2명까지만 탑승이 가능합니다.

 

핵심 포인트

 

보트의 최대 갯수는 사람의 숫자로 정해져있습니다.

때문에 정답은 다음과 같이 유추할 수 있습니다.

 

필요한 보트의 최대 갯수 - 2명이 보트를 함께 타는 경우

문제 풀이

 

1. people벡터를 정렬합니다.

        sort(people.begin(),people.end());

 

2. 필요한 변수들을 선언하고 다음과 같이 while문을 진행합니다.

        int left=0, right=people.size()-1, cnt=0; // 1
        while(left<right){ // 2
            if(people[left]+people[right]<=limit){ // 3
                left++;
                right--;
                cnt++;
            }
            else right--; // 4
        }

(1)  cnt는 두 사람이 함께 보트를 타는 경우를 저장하는 변수입니다.

(2) left < right의 조건까지 while문을 진행합니다.

(3) 만약 현재 people[right]의 무게와 people[left]의 무게가 limit이하라면... 

-> 보트 한대로 두 사람이 나눠타는 경우를 의미합니다. left는 +1, righr은 -1, cnt는 +1 합니다.

(4) 반대의 경우...

-> 한 명이 보트를 한 대 탑승해야하는 경우입니다. right의 값만 -1 해줍니다.

참고로 여기서 left는 움직임이 없는 이유는, left는 정렬로 인해 무게가 작은 사람을 가리키고 있기 때문입니다. 무게가 무거운 사람만 보트를 한대 할당해주면 되빈다.

 

3. 정답을 리턴합니다.

        return people.size()-cnt;

 

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(),people.end());
        int left=0, right=people.size()-1, cnt=0;
        while(left<right){
            if(people[left]+people[right]<=limit){
                left++;
                right--;
                cnt++;
            }
            else right--;
        }
        return people.size()-cnt;
    }
};