[프로그래머스] 구명보트 (그리디) / javascript

https://programmers.co.kr/learn/courses/30/lessons/42885?language=javascript

그리디 알고리즘에 속하는 문제이고
접근 방식도 어렵지 않았지만,, 효율성에서 헤매서 기록해본다

접근 방식

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
가 핵심이다.

어떻게 하면 구명보트를 최대한 적게 사용할 수 있을까??
-> 구명보트의 limit 만큼을 최대한 꽉 채워서 운반해야지 최대한 적게 사용할 수 있다.
-> 제일 무거운사람과 제일 가벼운 사람을 조합하는것이 구명보트를 꽉 채우는 방법이다.
-> 그러기 위해 내림차순으로 조합한후 양끝값(가장무거운사람, 가장가벼운사람)을 더해서 limit보다 작으면 옮기면되고, 아닐때에는 맨 앞 값(가장 무거운사람)만 넣어서 옮긴다!

코드 (정확성 통과, 효율성 실패)

function solution(people, limit) {
    var answer = 0;
    people.sort((a,b)=>b-a); // 내림차순 정렬
    
    while(people.length!==0){
        let fat=people.shift();
        let skinny=people[people.length-1];
        answer++;
        
        if(fat+skinny<=limit){
            people.pop();
        }
    }
   
    return answer;
}

위의 코드로 하면 효율성에서 실패된다 ㅠ.ㅠ

최종 코드

O(n) 시간복잡도를 가지는 shift() 메소드를 제거하고
for문을 사용하여 인덱스 범위를 좁히는 방법으로 개선하였다.

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