Level 2. 구명보트

Level 2. 구명보트

 

 

배낭 문제에서 남는 공간을 최소화하기 위해서는 부피가 큰 물건부터 넣어야 하듯이, 이 문제에서도 몸무게가 많이 나가는 사람부터 보트에 태워야 한다.

 

앞뒤에서 삭제가 빈번하므로, vector 대신 deque을 사용했다.

 

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit)
{
    int answer = 0;
    deque<int> deq(people.begin(), people.end());

    sort(deq.begin(), deq.end());

    do
    {
        int total = limit;
        bool bSuccess = false;

        while (!deq.empty() && (deq.back() <= total))
        {
            total -= deq.back();
            deq.pop_back();
            bSuccess = true;
        }

        while (!deq.empty() && (deq.front() <= total))
        {
            total -= deq.front();
            deq.pop_front();
            bSuccess = true;
        }

        answer += bSuccess;
    }
    while (!deq.empty());

    return answer;
}

 

직접 pop하지 않고 인덱스를 사용해 투 포인터로 해결해도 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit)
{
    int answer = 0;
    int l = 0, r = people.size() - 1;

    sort(people.begin(), people.end());

    do
    {
        int total = limit;

        while ((l <= r) && (people[r] <= total))
            total -= people[r--];

        while ((l <= r) && (people[l] <= total))
            total -= people[l++];

        answer += (total != limit);
    }
    while (l <= r);

    return answer;
}