구명보트

문제

접근법

people 요소를 sort를 하여 가장 큰 값을 하나 뽑아서 선택을 하고 작은 값들을 채워 넣는 방식을 생각을 하고 문제를 풀었다.

이 문제의 경우 n = 50000 으로 $O(nlogN)$ 안에 걸려 있다.

풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int cnt = 0;
    deque<int> dq;
    sort(people.begin(),people.end());
    for(int i=0;i<people.size();i++)
    {
        dq.push_back(people[i]);
    }
    
    while(!dq.empty())
    {
        cnt++;
        int last = dq[dq.size()-1];      
        int in_boat = last;
        
        dq.pop_back();
        
        while(!dq.empty())
        {
            int front = dq[0];
            if(in_boat + front <= limit)
            {
                dq.pop_front();
                in_boat += front;
            }
            else break;
        }
    }
    
    answer = cnt;
    
    return answer;
}

/*

한번에 최대 2명만 탈 수 있다. 무게 제한도 있다.

100kg가 제한이면 100kg까지 가능

사람들의 몸무게 : people,
무게제한 : limit

모든 사람을 구출 하기 위해 필요한 구명보트 수의 최솟값을 구하라

최대 5만명 nlogN 시간 이내에 해야한다.

사람의 몸무게는 40~240kg

구명보트의 무게제한은 40~240

sort를 해서 큰 값과 작은 값을 매칭 시킨다.

*/

내 풀이의 경우 최악의 경우에는 $O(n^2)$의 시간이 걸리는 부분이 있다. while문을 두번 통과 하는 부분인데, 이 경우가 되는 이유는 최악의 경우에 대해서 $n^2$의 시간이 걸리는데 이런 경우는 희박하고
평균적으로는 $n$시간에 끝날 것이기 때문에 시간 효율성에서 걸리지 않고 통과한 것으로 보인다.

이 문제에서 deque 컨테이너를 사용했다. 가장 큰 값과 작은 값을 앞 뒤에서 빼와서 무언가 연산을 해주기 위해서는 deque 컨테이너가 가장 좋다고 생각을 했다.

먼저 deque 안에 people의 모든 요소를 넣어주고 sort를 해준다.

그리고 deque가 빌 때 까지 while문을 돌면서 deque의 마지막 요소를 제거해주고 이를 저장해준다.
그리고 보트의 개수인 cnt의 값에 1을 더해준다.

그리고 첫번째 요소를 더했을 때가 limit과 비교해서 작거나 같은지를 확인하고 이에 대응하면
첫번째 값을 in_boat에 추가를 해주고 다음 첫번째 요소를 똑같은 방식으로 확인을 한다.

그렇지 못하여 else문으로 들어가게 되면 break으로 while문을 탈출한다.

이제와서 보니 문제를 잘 못 풀었다. 이 문제의 조건에서 보면은 보트는 최대 2명만 탈 수 있다고 했는데, 이를 고려하지 않았다. 어쩐지 안될것 같았는데 돼서 이상했는데.. 문제를 잘 보자..