[프로그래머스][C++] 구명보트

구명보트

문제 링크

구명보트

분석

모든 사람을 구명보트를 통해 옮길 수 있는 최소 개수를 구해 반환해야합니다.

구명보트의 특징은 다음과 같습니다.

• 최대 2명까지 태울 수 있다.
• 최대 무게 제한이 있다.
• 각 사람의 몸무게와 구명보트의 무게 제한은 최솟값과 최댓값이 정해져있다.
• 구명보트의 무게 제한은 항상 모든 사람의 무기 중 최댓값보다 크거나 같게 주어진다.

이를 통해 고려해야할 점은 다음과 같습니다.

구명보트에 태울 수 없는 사람은 존재하지 않으므로, 각 사람이 보트에 탑승할 수 있는지는 확인이 불필요합니다.
보트에는 최대 2명까지 태울 수 있지만, 최대 무게 제한이 있기 때문에 1명만 탑승 가능한 경우가 있습니다.
보트는 무게와 탑승 인원을 제외하면 다른 제한이 없으며 탑승 기준은 무게가 된다.

이를 통해 무게를 기준으로 오름차순 혹은 내림차순으로 정렬하여 보트에 태우면 된다는 것을 알 수 있습니다.
이때 보트에 태우는 기준은 다음과 같이 될 수 있습니다.

• 가장 무거운 사람 + 다음으로 무거운 사람
• 가장 무거운 사람 + 가장 가벼운 사람
• 가장 가벼운 사람 + 다음으로 가벼운 사람

이 중 가장 무거운 사람과 가장 가벼운 사람을 태울 경우 보트 수를 줄이거나 적어도 증가시키지 않습니다.
그 이유는 가장 무거운 사람은 몸무게의 값이 크기 때문에 같이 탈 수 있는 사람이 제한적이며, 무거운 사람들과 타고자 한다면 대부분 무게 한도를 초과해 더 많은 보트를 필요로하게 될 것입니다.
만약 가벼운 사람과 함께 타고자 한다면 상대적으로 무게 한도를 덜 초과할 것이고, 이로인해 상대적으로 적은 보트를 필요하게 될 것입니다.
하지만, 모든 사람이 보트의 제한보다 절반 이하의 몸무게 값을 가질 경우 가장 무거운 사람도 항상 다른 사람과 함께 탈 수 있어 다른 방식으로 보트를 태운 것과 같은 결과를 낼 것입니다.

가장 무거운 사람과 가장 가벼운 사람을 알고있기 위해서는 투 포인터를 활용하는 것이 좋습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    // 내림차순 정렬
    sort(people.begin(), people.end(), greater());
    
    // 투 포인터
    int left = 0;
    int right = people.size() - 1;
    
    // 필요한 보트 수를 구하는 반복문
    // 인원이 홀수일 수 있으므로, 마지막 사람까지 반복
    while (left <= right)
    {
        // 필요한 보트 수 증가
        ++answer;
        
        // 가장 무거운 사람을 태운 현재 보트의 무게
        int weight = people[left];
        
        // 다음으로 가장 무거운 사람을 가리키도록 인덱스 수정
        ++left;
        
        // 가장 가벼운 사람을 태울 수 있는 경우
        if (weight + people[right] <= limit)
        {
            // 가장 가벼운 사람을 태웠다고 가정하여 다음 인덱스를 가리킨다.
            --right;
        }
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n log n + n)$입니다.

• 정렬 함수 $O(n log n)$
• 필요한 보트 수를 구하는 반복문 $O(n)$
• $O(n log n) + O(n)$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.17ms, 4.2MB)
테스트 2 〉 통과 (0.10ms, 4.15MB)
테스트 3 〉 통과 (0.12ms, 4.15MB)
테스트 4 〉 통과 (0.12ms, 4.14MB)
테스트 5 〉 통과 (0.07ms, 3.7MB)
테스트 6 〉 통과 (0.04ms, 4.03MB)
테스트 7 〉 통과 (0.07ms, 3.68MB)
테스트 8 〉 통과 (0.02ms, 4.21MB)
테스트 9 〉 통과 (0.02ms, 4.21MB)
테스트 10 〉 통과 (0.11ms, 3.67MB)
테스트 11 〉 통과 (0.11ms, 4.21MB)
테스트 12 〉 통과 (0.09ms, 4.18MB)
테스트 13 〉 통과 (0.11ms, 4.2MB)
테스트 14 〉 통과 (0.14ms, 4.15MB)
테스트 15 〉 통과 (0.02ms, 3.74MB)
테스트 16 〉 통과 (0.01ms, 4.16MB)
테스트 17 〉 통과 (0.01ms, 4.02MB)
테스트 18 〉 통과 (0.01ms, 4.22MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)
테스트 20 〉 통과 (0.01ms, 4.14MB)
테스트 21 〉 통과 (0.01ms, 4.2MB)
테스트 22 〉 통과 (0.01ms, 4.14MB)

효율성 테스트

테스트 1 〉 통과 (1.57ms, 4.72MB)
테스트 2 〉 통과 (1.47ms, 4.63MB)
테스트 3 〉 통과 (1.45ms, 4.72MB)
테스트 4 〉 통과 (1.14ms, 4.78MB)
테스트 5 〉 통과 (1.14ms, 4.45MB)