[탐욕법] 구명보트

|| 문제설명 ||

1. 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 한다.
2. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있다.
3. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 한다.
4. 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성하라.

• people : 사람들의 몸무게를 담은 배열

• limit : 구명보트의 무게 제한

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

---

|| 문제해결과정 ||

1. for문: O(n)

people이 빌 때까지 반복

오름차순으로 정렬

( 가장 앞 + 맨 뒤 ) > 제한, 맨 뒤 제거 및 보트 개수 증가

( 가장 앞 + 맨 뒤 ) <= 제한, 둘 다 제거하고, 보트 개수 증가

---

|| 코드 ||

[2020.09.04] 실패

- O(n^2)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end(), compare);
    for(auto i = people.begin(); i != people.end();) {
        int chk = 0;
        for(auto j = i+1; j != people.end(); j++) {
            if(*i + *j <= limit) {
                people.erase(j);
                people.erase(i);
                chk = 1;
                break;
            }
        }
        if(!chk) people.erase(i);
        answer++;
    }
    return answer;
}

• 시간초과

---

[2020.09.04] 실패

- 중복for문 → while문 1개: O(n)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end(), compare);
    
    while(!people.empty()) {
        auto i = people.begin();
        auto j = people.end()-1;
        if(i == j) {
            people.erase(i); 
            answer++;
            break;
        }
        if(*i + *j <= limit) {
            people.erase(j);
            people.erase(i);
        }
        else people.erase(i);
        answer++;
    }
    return answer;
}

• 시간초과

---

[2020.09.04] 성공

- vector의 함수 erase는 지울때마다 재배열을 하기 때문에 시간이 오래 걸린다.
- erase 대신에 operator[]로 각각의 값들에 접근
	i, j를 생성해 맨앞, 맨뒤에 접근

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

int solution(vector<int> people, int limit) {
    int answer = 0, i = 0, j = people.size() - 1;
    sort(people.begin(), people.end(), compare);
    
    while(i<=j) {
        if(i == j) { 
            answer++;
            break;
        }
        if(people[i] + people[j] <= limit) {
            i++; j--;
        }
        else i++;
        answer++;
    }
    return answer;
}