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

구명보트를 최대한 적게 사용하여 사람들을 구출하기

 소 잃고 외양간 고치듯이 그리디 문제 풀어보기..~

 

문제 설명

무인도에 갇힌 사람들을 구명보트로 구출해야 하는 문제입니다. 각 구명보트에는 최대 두 명이 탈 수 있으며, 보트에는 무게 제한이 있습니다. 우리는 가능한 한 최소한의 보트를 사용하여 모든 사람을 구출해야 합니다.

 

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg인 경우, 2번째 사람(50kg)과 4번째 사람(50kg)은 같은 보트를 탈 수 있지만 1번째 사람(70kg)과 3번째 사람(80kg)은 같이 탈 수 없습니다. 이때 최소한 3개의 보트가 필요합니다.

 

문제 분석

이 문제는 최적화 문제로, 사람들의 몸무게를 고려하여 최소한의 구명보트를 사용하는 방법을 찾아야 합니다. 문제에서 주어진 조건은 다음과 같습니다:

• 각 보트는 최대 두 명이 탈 수 있고, 두 사람의 몸무게 합이 보트의 무게 제한을 넘지 않아야 합니다.
• 사람들의 몸무게는 40kg 이상 240kg 이하입니다.

이 문제는 그리디 기법을 사용하여 효율적으로 해결할 수 있습니다. 몸무게가 가장 가벼운 사람과 가장 무거운 사람을 짝지어 보트에 태우는 방식을 통해 보트 수를 최소화할 수 있습니다.

 

풀이 과정

1. 몸무게 순으로 정렬: 사람들을 몸무게가 큰 순서대로 정렬합니다. 이렇게 하면 무거운 사람을 먼저 처리하면서, 가벼운 사람과 짝지어 보트에 태울 수 있는지 확인할 수 있습니다.
2. 지점 설정: 배열의 앞부분은 무거운 사람(i), 뒷부분은 가벼운 사람(skinny)을 가리키는 두 포인터를 사용합니다.
3. 두 사람을 한 보트에 태울 수 있는지 확인: 현재 가장 무거운 사람과 가장 가벼운 사람의 몸무게 합이 보트의 제한을 넘지 않으면, 두 사람을 한 보트에 태우고 skinny 포인터를 앞으로 이동시킵니다. 만약 넘으면 무거운 사람만 태우고 다음으로 넘어갑니다.
   1. 여기서 각 보트에는 최대 2명까지만 탈 수 있으니 더 이상의 가벼운 사람이 탈거라는 생각은 안해도 됩니다. ((제가 바보같이 했었음.. 문제를 똑바로 읽자!!))
4. 보트 수 카운트: 위 과정을 반복하여 필요한 보트의 개수를 카운트합니다.

 

코드 구현

function solution(people, limit) {
    let count = 0;
    // 사람들의 몸무게를 내림차순으로 정렬
    people.sort((a, b) => b - a);
    
    // 가장 가벼운 사람을 가리킬 skinny 포인터
    let skinny = people.length - 1;
    
    // 무거운 사람부터 차례대로 보트에 태움
    for (let i = 0; i <= skinny; i++) {
        // 가장 무거운 사람과 가장 가벼운 사람을 짝지을 수 있으면
        if (people[i] + people[skinny] <= limit) {
            skinny--;  // 가장 가벼운 사람을 보트에 태우고 skinny 포인터 이동
        }
        // 보트 수 증가
        count++;
    }
    
    return count;
}