[프로그래머스]구명보트 C++ - Greedy 알고리즘

문제를 풀다보니 완전탐색, greedy알고리즘 등등.. 너무 취약한 것 같아서 풀이법을 정리해보려고 한다...

문제

조건

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람을 구출할 수 없는 경우는 없습니다.

입출력 예

---

먼저 생각한 풀이 방법
우선 무게가 적은 것끼리 합했을 때 함께 태울 수 있는 경우가 많아질 것 같아서 오름차순으로 정렬을 했다.
그 다음, 한 보트에 최대 두명만 탈 수 있기 때문에 인덱스를 하나씩 증가해가면서 두개를 더한 무게를 Limit값과 비교하며 보트의 개수를 +1하는 방식으로 풀었으나, 실패만 잔뜩.. 처음에는 deque나 queue를 써야하나 고민하기도 했다.
고민하다가 모르겠어서 풀이를 참고!

풀이 방법
1. 오름차순으로 정렬한다.
2. 맨 앞에 값인 최솟값과, 맨 뒤에 값인 최댓값을 이용하여 문제를 해결
3. 맨 뒤에 있는 값을 먼저 pop하고 맨 앞부터 비교하며 limit를 벗어나는지 검사한다.

앞에 idx와 맨 뒤에 값을 더했을 때 limit보다 크면 idx는 움직이지 않고 맨 뒤에 있는 값만 pop한다.
만약, 두 값을 더했을 때 Limit보다 작거나 같으면 idx도 한칸 움직이고 맨 뒤에 있는 값도 pop하며 보트의 개수를 추가한다.

코드

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

using namespace std;
//최대 두명 탈 수 있고 못타면 한명씩 타야함.
int solution(vector<int> people, int limit) {
    int answer = 0;
    int idx = 0;
    sort(people.begin(), people.end()); 
    while(people.size() > idx) {
        int back = people.back();
        people.pop_back();
        if(people[idx] + back <= limit) {
            answer++;
            idx++;
        }
        else answer++; //혼자타는 경우
    }
    
   
    return answer;
}

🐥pop하는 방식을 처음에 생각하긴 했지만 vector에서 pop보다 queue에서 pop이 더 익숙해서 방식을 떠올리지 못했다. vector에 대해 조금 더 익숙해져야겠다.