[C++] Interview Question : Find Minimum Canoe

| Question 

If a canoe can hold 2 kids and a max weight of 150 lbs, write a function that returns the minimum number of canoes needed, given a list of kids and their weights.

 

번역 :

하나의 카누에는 2명의 아이를 탑승시킬 수 있고, 카누의 최대하중은 150 lbs이다. 아이들의 무게를 나타내는 list가 주어질 때 필요한 카누의 수가 최소가 되는 함수를 작성하라. 

---

| Solution

문제를 풀 때 고려한 사항

• 아이들이 0명일 때 알고리즘이 정상 동작해야 한다.
• 아이들의 무게는 lsb단위로 주어진다고 가정한다. 
• 아이들이 홀 수 일 때와 짝수일 때 모두 함수가 정상 동작해야 한다.
• 무게가 150 lsb을 넘는 아이는 없다고 가정한다. 

생각해본다면 보트당 2명 탑승이 가능하니 최소 수는 ( 아이들의 수 / 2 )에 아이들이 홀 수 일 경우 1개를 더 해야 한다. 
즉, 아이들의 수를 n이라 했을 때 가능한 범위는 (n/2) + (n%2) <= ans <= n이다.

Method1

2명을 태워야 하기 때문에, 무거운 아이와 가벼운 아이의 무게의 합이 150 lbs 이하일 때 같이 태울 수 있다. 
즉, kids 배열을 정렬 후 O(nlogn) + 가장 가벼운 아이와 무게 합이 150 lbs이하인 무거운 아이 한 명을 찾아, 그 기준으로 필요한 보트의 수를 찾아간다 그리고, 그 무거운 아이보다 더 무거운 아이들은 보트당 한 명씩 태워야 한다. 

int MinimumCanoe(vector<int> kids) {
    int n = kids.size();

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

    int boat = 0;

    int low = 0, high = n - 1;
    while(low <= high) {
        if(low == high) {
            boat++;
            break;
        }

        if(kids[low] + kids[high] > 150) high--;
        else{
            if(kids[low] + kids[high] <= 150) {
                boat++;
                low++, high--;
            } else {
                boat++;
                high--;
            }
        }
    }

    return boat;
}

• Time Complexity : O(nlogn)
• Space Complexity : O(1)