[Programmers/C++] 구명보트

시간 복잡도

• 투 포인터를 이용하므로 $O(N)$의 시간 복잡도가 발생합니다.

문제 접근법

• 사람들의 몸무게를 오름차순으로 정렬합니다.
• 가장 무거운 사람부터 구명보트에 태우고 가장 몸무게가 낮은 사람과 함께 탈 수 있는지 확인합니다.
• 함께 탈 수 있다면 무게가 작은 사람도 함께 태웁니다.
• 해당 횟수마다 구명보트를 1개 사용하므로 정답을 하나 증가시킵니다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end());
    
    int l=0;
    int r=people.size()-1;
    
    while(l<=r)
    {
        if(people[l]+people[r] <= limit)
            l++;
        
        r--;
        answer++;
    }
    
    return answer;
}