[알고리즘 풀이] 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

간단한 그리디(투포인터) 문제입니다.

 

a + b를 합쳐 n에 가까운 수를 만들어야합니다.

배열의 최대크기가 5만이기 때문에 하나하나 찾아 배열에서 제거하더라도 시간초과가 나지는 않겠지만 투포인터 방식으로 풀면 간단하면서도 빠르게 해결할 수 있을 것입니다.

 

투포인터를 위해 먼저 people을 정렬한 후 limit에 부합한다면 포인터를 움직여가는 식입니다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int N = people.size();
    sort(people.begin(), people.end());

    int left = 0;
    int right = N - 1;

    while (left <= right)
    {
        int sum = people[left] + people[right];
        if (sum <= limit)
        {
            ++left;
        }
        --right;
        ++answer;
    }
    return answer;
}