javaScript 그리디 알고리즘으로 최적해 구하기

문제 

무인도에 갇힌 사람들을 최소한의 구명보트를 사용하여 모두 구출하여라 
각 사람은 개별적인 몸무게를 가지고 있고, 구명보트는 최대 2명을 태울수 있으며 무게 제한이 있다 
최소한의 구명보트를 사용하여 모든 사람 구출

풀이 

function solution(people, limit) {
  function solution(people, limit) {
    people.sort((a, b) => a - b); // 몸무게가 가벼운 순으로 정렬

    let answer = 0;
    let left = 0;
    let right = people.length - 1;

    while (left <= right) {
        // 가장 가벼운 사람과 가장 무거운 사람을 함께 태우는지 확인
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--; // 가장 무거운 사람은 항상 태워야 함
        answer++;
    }

    return answer;


}

• 주어진 배열 people을 가벼운 순으로 정렬
  •  people[left] : 가벼운 사람 
  • people[right] : 무거운사람
  • 두 사람의 무게의 합이 구명보트의 무게 제한 limit 이하면 태우고, left 증가
  • 그렇지 않으면 가장 무거운 사람만 태우고 right 증가
• 위의 과정을 반복해 모든 사람을 구출할 때까지 진행
• 각 구명보트 사용은 한 번에 최대 2명의 살마을 태우기 때문에, 태운 횟수가 최소일 때 구명 보트의 개수도 최소
• 그리다 알고리즘 
  • 현재 상황에서 가장 좋아 보이는 선택을 계속해서 하는 알고리즘! 

다른 풀이

function solution(people, limit) {
    // 몸무게를 가벼운 순으로 정렬
    people.sort(function(a, b) {
        return a - b;
    });

    // i는 가장 가벼운 사람을 가리키는 인덱스, j는 가장 무거운 사람을 가리키는 인덱스
    for (var i = 0, j = people.length - 1; i < j; j--) {
        // 두 사람의 무게 합이 limit 이하이면 가장 가벼운 사람과 무거운 사람을 함께 태움
        if (people[i] + people[j] <= limit) {
            i++;
        }
    }    

    // 태운 사람들의 수를 제외한 나머지 사람들의 수가 구명보트의 수
    return people.length - i;
}