[Algorithm] 구명 보트- JavaScript

프로그래머스-구명 보트
난이도 : Level 2

▶ 문제

 

 

▶ 풀이

둘만 탈 수 있기 때문에 제일 몸무게가 무거운 사람과 가벼운 사람을 같이 태우는 로직으로 최적의 해를 구할 수 있다.

function solution(people, limit) {
    var answer = 0;
    // 사람들을 몸무게가 낮은 순으로 정렬한다. (높은 순으로 해도 상관 없음)
    people.sort((a, b) => b - a);
    let left = 0;
    let right = people.length - 1;
    // Left 와 Right 의 포커스를 옮겨가며 배의 수를 카운트한다.
    while(left < right) {
        if(people[left] + people[right] > limit) {
            left++;
        } else {
            left++;
            right--;
        }
        answer++;
    }
    // left 와 right 가 같을 경우(한 사람만 남을 경우 배가 한 척 더 필요하다.)
    if(left === right) answer++;
    return answer;
}

▶ 삽질

모든 사람을 태우기 위한 로직

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