[Level2][Javascript] 구명보트

function solution(people, limit) {
    var answer = 0;
    people.sort(function(a,b){return a-b});
    let a=0;
    while(people.length){
        let weight = people.pop();
        let min_index= people.length;
        if(weight+people[min_index]>limit){
            answer++;
            continue;
        }
        for(let i= min_index;i>=0;i--){
            if(limit-weight>people[i]){
                min_index=i;
            }
            if(limit-weight===people[i]){
                min_index=i;
                break;
            }
        }
        people.splice(min_index,1);
        answer++;
    }
   
    return answer;
}

시간상 통과가 안되는 풀이다. 정답은 맞으나 더 효율적인 풀이 존재. 투 포인터로 풀어야 한다.

그리디의 성질을 만족하고 있기 때문에 탐욕적으로 풀면 된다. 굳이 limit에 가까운 두 쌍을 찾을 필요가 없다.

 

하기의 풀이는 타인의 풀이다.

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

    return answer;
}