구명보트 (c++)

문제

프로그래머스

구명보트에는 최대 2명이 탈 수 있고, 몸무게가 limit을 넘으면 안됩니다. 

구명보트를 최소로 하는 갯수를 구하라.

처음에는 단순히 people를 정렬해서 구하는 줄 알았지만, 시간초과가 나오게 되고

검색을 통해 투 포인터를 사용하는 것을 알게 되었다.

오름차순으로 정렬했기 때문에 가장 왼쪽에는 작은 몸무게, 가장 오른쪽은 큰 몸무게 이다.

l, r을 사용했다.

people[l] + people[r] <= limit이면 구명보트를 하나 늘려주고, l++, r-- 해준다.

만약 people[l] + people[r] > limit 이면 가장 큰 몸무게는 혼자 구명보트를 타야하기 때문에 r--만 해주고 구명보트를 늘려준다.

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

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