문제

Programmers, 구명보트

핵심

• 입력의 크기가 $50,000$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 무인도에 갇힌 사람들을 구명보트로 구출해야 한다. 구명보트에는 무게 제한이 있으며 최대 2명을 태울 수 있다. 구명보트를 최소한으로 사용하여 모든 사람을 구출할 때 구명보트의 최솟값을 구해야 한다.

잘못된 이진탐색 풀이

• 먼저 가장 무거운 사람을 태우고 난 뒤 남은 공간에 가장 가까운 무게인 사람을 태우려고 시도했다. 이를 찾기 위해서 전체를 탐색하면 $N^2$으로 시간 초과가 예상되었다. 따라서 이진탐색을 이용하면 $N \times logN$에 탐색할 수 있다고 생각하여 다음과 같이 구현하였다.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());
    int n = people.size();
    int ans = 0;
    while (!people.empty()) {
        int rest = limit - people.back();
        ++ans;
        people.pop_back();
        auto it = lower_bound(people.begin(), people.end(), rest + 1);
        if (it != people.begin()) {
            --it;
            if (*it <= rest)
                people.erase(it); 
        }
    }
    return ans;
}

• 효율성 부분에서 2개의 테스트케이스가 시간초과가 되었다. 시간복잡도가 $O(N \times logN)$이라고 생각했지만, vector에서 임의의 위치에서 erase를 하는 것은 $O(N)$이므로 $O(N^2 \times logN)$으로 볼 수 있다. N이 최대 50,000 이기에 시간 초과가 난다.
• 이진 탐색 코드에서 눈여겨볼 사항은 rest에 + 1을 한 것이다. rest 이하의 무게를 찾는 사람을 찾아야 하는데, lower_bound는 x 이상의 수를 반환한다. 따라서 rest + 1 이상의 수를 찾은 다음 그 이전 수를 반환하도록 하였다.

그리디 투 포인터 풀이

• 가장 무거운 사람과 가장 가벼운 사람을 같이 태우면 최소 구명보트 개수를 만족시킨다는 명제를 참으로 보아 문제에 접근한다. 가장 무거운 사람과 남은 무게에 가장 가까운 사람을 태워야 할 것 같지만 가장 가벼운 사람을 태우는 것만으로도 최적해가 달성된다. 가장 무거운 사람(A)과 남은 공간에 가장 딱 맞는 사람(B)를 태울 수 있다면 가장 가벼운 사람(C)도 태울 수 있기 때문이다.
• 해당 명제는 보트에 최대 2명이 탈 수 있다는 조건하에 최적해를 보장하는 것을 명심하자.

개선

코드

시간복잡도

• $O(N)$

C++

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

using namespace std;
int solution(vector<int> people, int limit) {
    sort(people.begin(), people.end());
    int l = 0;
    int r = people.size() - 1;
    int ans = 0;
    while (l <= r) {
        ++ans;
        int rest = limit - people[r];
        if (rest >= people[l])
            ++l;
        --r;
    }
    return ans;
}

Java

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int l = 0;
        int r = people.length - 1;
        int ans = 0;
        while (l <= r) {
            ++ans;
            int rest = limit - people[r];
            if (rest >= people[l])
                ++l;
            --r;
        }
        return ans;
    }
}