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

최대한 적은 수의 구명보트를 사용하여 사람들을 모두 구출하는 문제다.

 

최적의 방법이 존재하는 문제임을 눈치채기가 쉽지 않았다..ㅜㅜ

처음엔 limit이 100이면 40 태우고 60있나 찾고, 다음엔 60보다 작은 최댓값 찾아서 짝을 만들어주려 했다..

 

훨씬 간단한 방법이 존재한다.

 

우선 내림차순으로 people을 정렬한다.

 

[100 60 50 51 40 30] limit=100 이라면

1. 제일 무거운 사람(left)과 제일 가벼운 사람(right)의 무게를 더했을 때, limit보다 크다면, 제일 무거운 사람만 태울 수 있다.

  => 태웠으므로 left++

2. 제일 무거운 사람과 제일 가벼운 사람의 무게를 더했을 때, limit보다 작다면, 둘 다 태울 수 있다.

  => 둘 다 태웠으므로 left++, right--

이렇게 index를 옮겨가며 검사하면 된다.

people[left]	people[right]	sum > limit	result
100	30	sum=130, true	left++
60	30	sum=90, false	left++, right--
50	40	sum=90, false	left++, right--
50	51	sum=101, true	left++

여기까지 하면 left = 3, right = 3으로 while문을 벗어나게 된다.

하지만 한명 남았으므로, 새로운 배가 하나 더 필요하다.

그러므로 left == right인 경우 answer++해준다.

 

function solution(people, limit) {
    var answer = 0;
    // 내림차순 정렬
    people.sort((a,b) => b-a);
    console.log(people);
    let left = 0;
    let right = people.length -1;
    
    while(left < right){
        console.log('새로운 배를 띄움')
        // 두명까지만 탈 수 있으므로...
        const sum = people[left] + people[right];
        // 무게가 넘치면 (left만 배에 태우고) 다음 사람을 검사한다.
        if(sum > limit){
            console.log(people[left], '를 배에 태웠습니다.')
            left++;
        } else {
            // 무게가 넘치지 않으면 (둘다 태우고) 다음 사람을 검사한다.
            console.log(people[left],'와', people[right], '를 배에 태웠습니다.')
            left++;
            right--;
        }
        answer++;
    }
    // 한명 남은 경우 배 하나가 더 필요하다.
    if(left == right) answer++;
    return answer;
}

 

이 방법을 사용하면서 걱정했던 점은

people = [60, 40, 30] limit=100 처럼

60-40의 짝이 존재하는데 60-30의 짝을 태우게 되는 경우가 있지 않을까? 그래서 비효율적으로 태우게 되면 어쩌지? 하는 걱정이었다.

 

그러나 이런 경우에도.. 정렬이 되어있기 때문에 답이 달라지진 않는다.

60-30을 태웠을때 문제가 되려면 70처럼 30의 더 적절한 짝이 있어야 하는데

그런 경우엔 내림차순 정렬 때문에  

people = [70, 60, 40, 30] 

70-30, 60-40이 타게 되기 때문에... 걱정하지 않아도 된다.