23.04.03. 풀었던 문제들

Leetcode 881. Boats to Save People

 two pointer + greedy 문제.

 각 boat에 최대 2명의 인원이 올라가고, limit보다 넘으면 안 되므로 오름차순 정렬한 이후 제일 큰 것을 올리고, 이후 작은 것을 올릴 수 있으면 올린다. 이것을 반복하면 된다.

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end(), less<int>());
        int s = 0, e = people.size()-1;
        int answer = 0;
        while(s<=e){
            int sum= people[e];
            e--; answer++;
            if(sum + people[s] <= limit){
                s++;
            }
        }
        return answer;
    }
};

 

시간복잡도

 정렬에 O(nlogn), two-pointer에 O(n)이므로 O(nlogn)이다.