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

문제 요약

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 이때 구명보트에 탈수있는 인원은 최대 2명, 무게 제한 limit도 존재합니다. 사람들의 몸무게를 담은 배열 people와 무게제한 limit가 매개변수로 주어질때, 모든 사람을 구출하기 위한 최소한의 구명보트의 수를 return하는 함수를 작성하시오.

 

나의 생각

처음 문제를 풀때는 인원 제한이 2명이 존재한다는 것을 알지 못하고 구현하였습니다. 문제 요약을 작성하면서 2명 제한이 있는 것을 발견하였기 때문에 이 부분은 문제를 해결할때 적용이 되지 않았지만 문제 해결은 되었습니다.

 

먼저 무게가 많은 사람부터 적은 순으로 정렬하였습니다. 구명 보트의 무게제한때문에 무게가 많이 나가는 사람은 다른 사람과 함께 탑승할 가능성이 적기 때문에, 무게가 많이 나가는 사람을 우선적으로 탑승 후 남은 무제제한에 맞추어 무게가 적게 나가는 사람을 탑승하는 방법으로 생각하였습니다.

 

 

처음에는 아래와 같은 순서대로 구현하였습니다.

(1) 내림차순으로 정렬

(2) 무게 제한을 넘어서지 않는다면 배열 앞에서부터 탑승

(3) 무게 제한을 넘어선다면 배열을 reverse

(4) reverse 상태에서도 무게 제한을 넘어선다면 1개의 구명보트 완성 및 초기화

 

 

앞서 설명했듯이 인원제한 2명을 알지 못한 상태로 문제를 풀었기 때문에 무게제한을 넘어서지 않는 다면 구명 보트에 계속 탑승을 하는 코드입니다. 위와 같이 구현했을 때 정확성테스트는 통과했으나 효율성에서는 통과하지 못했습니다.

 

 

reverse 대신 인덱스 사용하기

reverse 메서드를 사용하는게 시간 초과의 원인이라고 생각하였기 때문에 인덱스를 사용하기로 합니다. 배열의 앞에서와 뒤에서 모두 추출하기 때문에 first, last 두개의 인덱스를 사용하였습니다. 그리고 현재 앞 또는 뒤 어느쪽에서 접근할지를 나타내는 reverse 상태를 사용하였습니다.

 

🔓 코드 구현 순서는 아래와 같습니다.

 

(1) 내림차순으로 정렬

(2) 무게 제한을 넘어서지 않는다면 first 인덱스에서부터 탑승

(3) 무게 제한을 넘어선다면 reverse 상태를 사용하여 last인덱스에서부터 탑승

(4) reverse 상태에서도 무게 제한을 넘어선다면 1개의 구명보트 완성 및 초기화

 

function solution(people, limit) {
    people.sort((a, b) => b - a);
    let count = 0;
    let sum = 0;
    let reverse = false;
    let first = 0;
    let last = people.length - 1;

    while (first <= last) {
        const w = people[reverse ? last : first];

        if (sum + w > limit) {
            if (reverse) {
                sum = 0;
                count += 1;    
            }

            reverse = !reverse;
            continue;
        }

        sum += w;

        if (reverse) {
            last -= 1;    
        } else {
            first += 1;
        }

    }

    return count += 1;
}