救命ボート

コード#コード#

[マイコード]-効率チェックに失敗しました

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

int solution(vector<int> people, int limit) {
    int answer = 0, free = limit, tmp;
    pair<int, int> dif;
    sort(people.begin(), people.end());
    for(int i=0;i<people.size();i++)
    {
        /* limit보다 큰 경우는 이미 탄 사람 */
        if(people[i] > limit) continue;
        answer++;
        free = limit - people[i];
        dif = {-1,limit};
        /* 같이탈 수 있는 사람들 중, 가장 효율적 탑승이 가능한 사람 찾기 */
        for(int j=people.size()-1;j>=0;j--)
        {
            tmp = free-people[j];
            if(tmp >=0 && dif.second > tmp){
              dif = {j, tmp};
                break;
            } 
        }
        /* 같이 탈 수 있는 사람이 있는 경우 */
        if(dif.second < limit) 
            people[dif.first] = limit+1;
    }
    return answer;
}

[最適コード]

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

int solution(vector<int> people, int limit) {
    int answer = 0, head = 0, tail = people.size()-1;
    /* 오름차순 정렬 */
    sort(people.begin(), people.end());

    while(head <= tail)
    {
        answer++;
     /* 어차피 한명은 타야하는데, 반드시 무거운 애가 타야함!
       --> 크기가 작은 애들끼리 있을 때 함께 탈 확률이 크기 때문! (tail-- 필수 / head++ 선택) */
        if(people[head] + people[tail--] <= limit) head++;
    }
    return answer;
}