[프로그래머스/C++] 구명보트 : Greedy

문제

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

풀이

무게 순서대로 정렬
젤 앞에랑 젤 뒤에 같이 탈 수 있으면 같이 보트 태우기
같이 못 탄다면 젤 무거운 사람 혼자 보트 태우기

✨처음에 배열에서 원소를 삭제하는 방식으로 구현했는데 자꾸 시간초과 났다. 인덱스 이용하는 방식으로 효율성 문제 해결

코드

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


using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int l = 0;
    int h = people.size() - 1;
    sort(people.begin(), people.end());
    
    while(l <= h) {
        if(l == h) { //한명만 남은 경우
            answer++;
            break;
        }
        
        if (people[l]+people[h] > limit) {
            h--;
            answer++;
        }
        else {
            l++;
            h--;
            answer++;
        }  
    }
    
    return answer;
}