프로그래머스 - 구명보트(c++, javascript) [탐욕법]

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

 

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

 

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

 

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

입출력 예

 

풀이

내가 처음 생각한 방식은

먼저 people을 오름차순으로 정렬을 한 후에 맨 앞(가장 적은 무게)과 맨 뒤(가장 큰 무게)의 값을 비교해가며

limit과 비교해 혼자 태울지 쌍으로 태울지 결정하여 보트에 태운 후, 벡터에서 제거해 나가는 방식이었다.

(처음엔 이렇게 무식하게 풀었다.)

 

c++

/*
* 
*     통과하지 못하는 코드
*
*/

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    // 오름차순 정렬
    sort(people.begin(), people.end());
    
    while(!people.empty()){
    	
        // 1명만 남으면 1명 태우고 종료
        if(people.size()==1) {
            ++answer;
            break;
        }
        
        // 가장 적게 나가는 몸무게에 2배 했을 때 limit보다 크다면
        // 남아 있는 사람들 그 누구도 동시에 태울 수 없다.
        // 따라서 남아 있는 사람들은 1명씩 태워야 한다. ( size 만큼 태워야 한다. )
        if(people[0]*2 > limit){
            answer += people.size();
            break;
        }
        
        // 맨 앞(가장 적은 무게)의 무게를 고정하고 맨 뒤(가장 큰 무게)부터 앞으로 탐색한다.
        for(int j=people.size()-1; j>0; --j){
            int two_weight = people[0] + people[j];
            
            // 고정 된 맨 앞의 무게와 더해 limit 안쪽이면
            // 둘이 동시에 보트에 태운다.( erase로 둘다 지운다. )
            if(two_weight <= limit){
                ++answer;
                people.erase(people.begin());
                people.erase(people.begin()+j-1);
                break;
            }
            
            // 둘이 동시에 태울 수 없다면 
            // 한명만 태운다.
            if(j == 1){
                ++answer;
                people.erase(people.begin());
            }
        }
    }
    return answer;
}

 

하지만 역시나 시간초과가 발생!

 

큐로 해결할 수 있을 거 같아서 다시 풀었다.

내가 생각한 핵심적인 생각은 어떤 사람들의 무게가 limit값의 절반 이하라면

이 사람들은 다른 모든 사람들과 보트에 동승할 수 있는 '가능성'이 있다.

 

하지만 어떤 사람들의 무게가 limit값의 절반을 초과하면

이 사람들끼리는 보트에 같이 탈 수가 없다.

 

이 생각을 기반으로 limit값의 절반을 기준으로

limit값의 절반 이하인 사람들의 무게를 min 힙에 넣었고

limit값의 절반 초과인 사람들의 무게를 max 힙에 넣었다.

 

min 힙과 max 힙의 top끼리 비교해 나간다면

문제를 해결할 수 있다.

 

c++

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    priority_queue<int,vector<int>,greater<int>> min_q;
    priority_queue<int,vector<int>,less<int>> max_q;
    
    // 사람들을 limit을 기준으로 반으로 나눈다.
    // limit의 절반보다 같거나 작다면 min heap에 담고
    // limit의 절반보다 크다면 max heap에 담는다.
    for(auto ele:people){
        if(ele <= limit/2) min_q.push(ele);
        else max_q.push(ele);
    }
    
    while( !( min_q.empty() && max_q.empty() ) ){
    
    	// max쪽 사람들이 모두 구출됐다면
        // min쪽 사람들은 모두 짝지어 갈 수 있으므로 
        // 짝수이면 현재 인원의 절반만큼 보트가 필요하고
        // 홀수이면 현재 인원의 절반보다 1개 더 많은 보트가 필요하다.
        if(max_q.empty()){
            int odd_or_even = min_q.size()%2;
            if(odd_or_even==0) answer += min_q.size()/2;
            else answer += min_q.size()/2 + 1;
            break;
        }
        
        // min쪽 사람들이 모두 구출됐다면
        // max쪽 사람들은 혼자서만 탈 수 있으므로 max쪽 사람들의 인원수 만큼 보트가 필요하다.
        if(min_q.empty()){
            answer += max_q.size();
            break;
        }
        
        // 무게가 가장 적게 나가는 사람(min)과 가장 많이 나가는 사람(max)의 무게를 더한다.
        int min = min_q.top();
        int max = max_q.top();
        int weight = min + max;
        
        // limit 안쪽이면 둘이 동시에 보트에 태운다. (pop으로 둘다 제거)
        if(weight <= limit){
            min_q.pop();
            max_q.pop();
        }else max_q.pop(); // limit을 초과하면 max인 사람은 다른 누구와도 같이 탈 수 없기 때문에 혼자 태워 보낸다.
        
        ++answer;
    }
    
    return answer;
}

 

javascript

function solution(people, limit) {
    var answer = 0;
    const min_arr = [], max_arr = [];
    
    people.sort((a,b)=>a-b);
    
    people.forEach((ele)=>{
        if(ele <= limit/2) min_arr.push(ele);
        else max_arr.push(ele);
    })
    
    let min_point = 0;
    let max_point = max_arr.length-1;
    
    while(true){
            if(max_point == -1 && min_point == min_arr.length) break;
            
            if(max_point == -1){
                const odd_or_even = (min_arr.length - min_point)%2;
                if(odd_or_even==0) answer += Math.floor( (min_arr.length - min_point)/2 );
                else answer += Math.floor( (min_arr.length - min_point)/2 ) + 1;
                break;
            }
        
            if(min_point == min_arr.length){
                answer += max_point + 1;
                break;
            }

            const min = min_arr[min_point];
            const max = max_arr[max_point];
            const weight = min + max;

            if(weight <= limit){
                ++min_point;
                --max_point;
            }else --max_point;

            ++answer;
    }
    
    return answer;
}

 

 

javascript 좋아요 많이 받은 분의 풀이

 

와 이렇게 간단하게 ...

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