|| 문제설명 ||
- 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 한다.
- 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있다.
- 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 한다.
- 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성하라.
- people : 사람들의 몸무게를 담은 배열
- limit : 구명보트의 무게 제한
_ 무인도에 갇힌 사람 : 1명 이상 50,000명 이하
_ 각 사람의 몸무게 : 40kg 이상 240kg 이하
_ 구명보트의 무게 제한 : 40kg 이상 240kg 이하
_ 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.
|| 문제해결과정 ||
- for문: O(n)
people이 빌 때까지 반복
오름차순으로 정렬
( 가장 앞 + 맨 뒤 ) > 제한, 맨 뒤 제거 및 보트 개수 증가
( 가장 앞 + 맨 뒤 ) <= 제한, 둘 다 제거하고, 보트 개수 증가
|| 코드 ||
[2020.09.04] 실패
- 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;
}
[2020.09.04] 실패
- 중복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;
}
[2020.09.04] 성공
- 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;
}