구명보트

코드

[ 나의 코드 ] - 효율성 검사 실패

#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;
}

• 같이 탈 수 있는 사람과 탔을 때, 가장 여유공간이 적게 남는 경우가 효율적!
• 해당 경우를 찾기 위해 이중 for문을 썼더니 효율성 검사에서 실패함

---

[ 최적의 코드 ]

#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;
}

• 같은 결과를 내지만 정렬 후 head / tail로 접근을 하면 훨~씬 빠르다! (..이런게 알고리즘의 힘인가)

• 주의해야 할 점은 반드시 tail에 해당하는 사람은 태워야 한다는 것이다!
  -> 무게가 적은 사람들 끼리 있을 때 함께 탈 수 있는 경우가 더 발생하기 때문
  [50 50 70 80] 일 때 head++를 하면 [50 70 80]이 되어서 효율적이지 않게 됨
  (50 50 은 같이 탈 수 있는데 안태웠기 때문ㅠ)

• 함께 타지 못하는 경우에, 반드시 무게가 무거운 사람이 타야한다
  --> 절대적인 특징 --> greedy algorithm