[프로그래머스] 구명보트

구명보트

🔍 알고리즘 분류

• 그리디

💡 문제 풀이

1. 몸무게 오름차순 정렬
2. start, end 인덱스 설정
3. 몸무게가 무거운 사람(end)부터 보트에 태우면서 첫 번째 사람start도 같이 태울 수 있는지 확인
4. 같이 태울 수 있다면 start++ (= 첫 번째 사람 태웠다는 의미), 없다면 그대로
5. end-- (= 마지막 사람 태웠다는 의미) 하며 start <= end 일 때까지 반복
6. 보트 1개 사용했으므로 answer++

📄 코드

• C++

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    // 오름차순 정렬
    sort(people.begin(), people.end());
    
    // 두 개의 인덱스 설정
    int start = 0;
    int end = people.size() - 1;
    
    while (start <= end) {
        // 마지막 사람이 보트를 탈 때 첫 사람도 탈 수 있으면 첫 사람의 다음 사람 확인
        if (people[start] + people[end] <= limit) start++;
        // 마지막 사람의 앞 사람 확인
        end--;
        // while 문 한 번 돌 때마다 보트 한 개씩 사용
        answer++;
    }
        
    return answer;
}