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

문제

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

시도했던 방법 & 결과

function solution(people, limit) {
    let cnt = 0;
    
    for (let i = 0; people.length; i++) {
        let leftWeight = limit - people[0]
        people.shift()
        cnt += 1
        
        for (let j = 0; j < people.length; j++){
            if (people[j] <= leftWeight) {
                people.splice(j, 1)
            }
        }
    }
    return cnt
}

첫번째 사람을 구명 보트에 태우고 배열을 순회하며 남은 무게보다 적게 나가는 사람을 찾아서 추가로 태우는 방법으로 접근했다. 테스트 중 몇 개만 맞고 나머지는 전부 실패로 떴다.

문제점

이렇게 풀면 구명보트의 최솟값을 구할 수 없다. 태울 수 있는 사람을 선착순으로 제거하기 때문이다. 무게가 적게 나가는 사람과 무게가 많이 나가는 사람을 조합해서 두 사람의 무게의 합이 구명 보트의 최대 무게에 근접해야 한다.

시도했던 방법 & 결과 2

function solution(people, limit) {
    let cnt = 0;
    let arr = people.sort((a, b) => b - a);
    for (let i = 0; arr.length; i++) {
        let heavy = arr[0]
        let light = arr[arr.length - 1]
        
        if (light + heavy <= limit) {
            arr.shift()
            arr.pop()
        } else {
            arr.shift()
        }
        cnt += 1
    }
    return cnt
}

배열을 무게가 많이 나가는 순서대로 정렬해서 무게가 가장 많이 나가는 사람 + 무게가 가장 적게 나가는 사람의 합이 구명 보트의 최대 무게를 초과하지 않으면 태우는 방법으로 바꾸었다. 만약 최대 무게를 초과하면 무게가 가장 많이 나가는 사람만 태운다. 정확성 테스트는 통과했는데 효율성 테스트 몇개를 통과하지 못했다.

문제점

if 문에서 배열의 요소를 계속 제거함으로써 배열의 구성을 변경하기 때문에 시간이 오래 걸리는 것 같았다. 그래서 배열은 그대로 두고 인덱스를 이동하는 방법으로 바꾸었다.

풀이

function solution(people, limit) {
    let cnt = 0;
    let arr = people.sort((a, b) => b - a);
    let first = 0
    let last = arr.length -1
    while (first <= last) {
        if (arr[first] + arr[last] <= limit) {
            first++
            last--
        } else {
            first++       
        }
        cnt += 1
    }
    return cnt
}

성공!