A.P - 구명보트(프로그래머스, L2)

1. 문제

• Greedy(탐욕법) 관련 문제
• 구출해야 할 사람들의 몸무게 배열과 구명보트의 무게제한이 주어짐
• 최소한으로 운행할 때, 몇번에 전부 구출할수 있는지를 리턴하라
• 최소 1명 이상을 구해야하고, 최대 몸무게가 무게제한을 넘지 않음

2. 수도코드

// 사람을 무거운 순으로 정렬하고
// 가장 무거운 사람부터 옮길때에 남은 무게에
// 가장 가벼운 사람이 실리는지를 계속 체크하고
// 같이 옮길 수 있는 무게가 나올때에 두명을 함께 운반하고
// 운반할 때마다 카운팅을 하도록 하고 카운터를 리턴하자

3. 시도

// 마지막에 혼자 남았을때의 엣지케이스가 존재하지만, 1회 탈출로 적용되므로 문제되지 않음
function solution(people, limit) {
    // 보트의 운행횟수의 카운터를 선언
    let cnt = 0;
    
    // 제공받은 사람들의 무게를 내림차순으로 정렬
    let sa = people.sort((a,b) => b-a);
    
    // 현재 내릴 사람의 위치를 저장
    let hp = 0;
    
    // 함께 내릴수 있는지 검사할 사람의 위치를 저장 
    let lp = people.length - 1;
    
    // while문으로 다 내릴때까지 반복하자
    // 현재 내릴 사람이 마지막 사람의 위치를 넘어가면 종료
    while (hp <= lp) {
        // 현재 내릴 무거운 사람과 제일 가벼운 사람을 더하고
        let sw = sa[hp] + sa[lp]; 
        // 리미트와 비교, 크면 혼자 작거나 같으면 함께 내리자
        if (sw > limit) {
            hp++;
        } else {
            hp++;
            lp--;
        }
        cnt++;
    }
    return cnt;
}

4. 레퍼런스

function solution(people, limit) {
    people.sort(function(a, b){return a-b});
    for(var i=0, j=people.length-1; i < j; j--) {
        if( people[i] + people[j] <= limit ) i++;
    }    
    return people.length-i;
}

5. 레퍼런스 공부 및 주석

// 반복문 조건부에 var i=0 을 활용하여 변수 사용을 최소화하였음
// 바깥에 카운터 변수를 따로 만들어 활용해도 가능할 것으로 보임
// 가벼운쪽인 j부터 하나씩 줄여가며 중복하여 내릴 수 있는 사람을 찾아감
// 중복하여 내릴 수 있는 사람이 나타나면 카운터 i값을 늘리고
// 총 인원에서 같이 내린 사람수인 i값을 빼서 리턴하는 형식
function solution(people, limit) {
    people.sort(function(a, b){return a-b});
    for(var i=0, j=people.length-1; i < j; j--) {
        if( people[i] + people[j] <= limit ) i++;
    }    
    return people.length-i;
}