- people : 사람들의 몸무게를 담은 배열
limit : 구명보트의 무게 제한
_ 무인도에 갇힌 사람 : 1명 이상 50,000명 이하
_ 각 사람의 몸무게 : 40kg 이상 240kg 이하
_ 구명보트의 무게 제한 : 40kg 이상 240kg 이하
_ 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.
- 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;
}
- 시간초과
- 중복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;
}
- 시간초과
- 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;
}