문제 소개
사람들의 몸무게가 담긴 people 배열이 주어집니다. i번째 사람의 무게는 people[i]이며, 각 보트는 최대 limit만큼의 무게를 실을 수 있습니다. 한 보트에는 동시에 최대 2명까지만 탑승할 수 있고, 이때 두 사람의 무게 합은 limit 이하여야 합니다.
목표는 모든 사람을 태우기 위해 필요한 최소 보트 수를 구하는 것입니다. 예를 들어 입력이 [3, 2, 1, 2]이고 limit이 3이라면, 다음과 같이 세 개의 보트가 필요합니다.
[(1, 2), (2), (3)]
접근 방법: 정렬 + 투 포인터 + 그리디
이 문제는 그리디(Greedy) 전략과 투 포인터(Two Pointer) 기법을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 가장 가벼운 사람과 가장 무거운 사람을 짝지어 보는 것입니다. 가장 무거운 사람이 가장 가벼운 사람과 함께 탈 수 없다면, 그 누구와도 함께 탈 수 없으므로 혼자 타야 합니다.
알고리즘 단계
people 배열을 오름차순으로 정렬합니다.
i := 0 (가장 가벼운 사람), j := 배열 크기 − 1 (가장 무거운 사람), ret := 0 (보트 수)으로 초기화합니다.
i <= j인 동안 반복합니다.
people[i] + people[j] <= limit이면 두 사람을 한 보트에 태울 수 있으므로 i는 1 증가, j는 1 감소시킵니다. 그렇지 않으면 가장 무거운 사람이 혼자 타야 하므로 j만 1 감소시킵니다.
매 반복마다 보트 하나를 사용했으므로 ret을 1 증가시킵니다.
반복이 끝나면 ret을 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int i = 0;
int j = people.size() - 1;
int ret = 0;
while(i <= j){
if(people[i] + people[j] <= limit){
i++, j--;
}else{
j--;
}
ret++;
}
return ret;
}
};
main(){
vector<int> v = {3,2,1,2};
Solution ob;
cout << (ob.numRescueBoats(v, 3));
}입력
[3,2,1,2] 3
출력
3
동작 과정 살펴보기
입력 [3, 2, 1, 2]를 정렬하면 [1, 2, 2, 3]이 됩니다. limit이 3일 때 동작 순서는 다음과 같습니다.
1번째 반복: people[0](1) + people[3](3) = 4 > 3이므로, 무게 3인 사람이 혼자 탑승 → 보트 1개 사용
2번째 반복: people[0](1) + people[2](2) = 3 ≤ 3이므로, 두 사람이 함께 탑승 → 보트 1개 사용
3번째 반복: 남은 무게 2인 사람이 혼자 탑승 → 보트 1개 사용
따라서 총 3개의 보트가 필요하며, 출력 결과와 일치합니다.
복잡도 분석
시간 복잡도: O(n log n) — 정렬에 O(n log n), 투 포인터 탐색에 O(n)이 소요됩니다.
공간 복잡도: O(1) — 추가 공간 없이 입력 배열을 제자리에서 정렬하여 사용합니다.