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

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42885

1차 접근

순차 탐색하여 방문하지않은 최적의 파트너를 태워서 이동하기

function solutionFail1(people, limit) {
    var answer = 0;
    people = people.sort().map(p => [p, 0]);
    people.forEach(([p, v], i) => {
        if (v) return;

        var nt = i + 1, target = i;

        while (nt < people.length && people[nt][0] + p <= limit) {
            if (!people[nt][1])
                target = nt;
            nt++;
        }
        if (target !== i)
            people[nt - 1][1] = 1;
        answer++;
    })
    return answer;
}

알고리즘이 잘못 되었는지 정확성도 20%, 효율성도 10%

코드

제일 작은 수와 제일 큰 수가 같이 갈 수 있으면 보내기

** JS에서는 기본적으로 [1,2,10] => [1,10,2] 이렇게 문자열 정렬된다.
sort((a,b) => a-b) 꼭 이렇게 사용하는 습관 갖자!

function solution(people, limit) {
    people = people.sort((a,b) => a-b);
    var answer = 0, idx = 0;
    while(idx < people.length){
        // 없어도 무방
        // if(people[idx] > limit/2){
        //     answer += people.length - idx
        //     break;
        // }
        var target = people.length - 1;
        if (people[idx] + people[target] <= limit)
            idx++;
        people.pop();
        answer++;
    }
    return answer;
}