Programers : 구명보트 (greedy)
10466 단어 level2PROGRAMERSPROGRAMERS
구명보트
코드
[ 나의 코드 ] - 효율성 검사 실패
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0, free = limit, tmp;
pair<int, int> dif;
sort(people.begin(), people.end());
for(int i=0;i<people.size();i++)
{
/* limit보다 큰 경우는 이미 탄 사람 */
if(people[i] > limit) continue;
answer++;
free = limit - people[i];
dif = {-1,limit};
/* 같이탈 수 있는 사람들 중, 가장 효율적 탑승이 가능한 사람 찾기 */
for(int j=people.size()-1;j>=0;j--)
{
tmp = free-people[j];
if(tmp >=0 && dif.second > tmp){
dif = {j, tmp};
break;
}
}
/* 같이 탈 수 있는 사람이 있는 경우 */
if(dif.second < limit)
people[dif.first] = limit+1;
}
return answer;
}
- 같이 탈 수 있는 사람과 탔을 때, 가장 여유공간이 적게 남는 경우가 효율적!
- 해당 경우를 찾기 위해 이중 for문을 썼더니 효율성 검사에서 실패함
[ 최적의 코드 ]
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0, head = 0, tail = people.size()-1;
/* 오름차순 정렬 */
sort(people.begin(), people.end());
while(head <= tail)
{
answer++;
/* 어차피 한명은 타야하는데, 반드시 무거운 애가 타야함!
--> 크기가 작은 애들끼리 있을 때 함께 탈 확률이 크기 때문! (tail-- 필수 / head++ 선택) */
if(people[head] + people[tail--] <= limit) head++;
}
return answer;
}
- 같은 결과를 내지만 정렬 후 head / tail로 접근을 하면 훨~씬 빠르다! (..이런게 알고리즘의 힘인가)
- 주의해야 할 점은 반드시
tail
에 해당하는 사람은 태워야 한다는 것이다!
-> 무게가 적은 사람들 끼리 있을 때 함께 탈 수 있는 경우가 더 발생하기 때문
[50 50 70 80] 일 때 head++를 하면 [50 70 80]이 되어서 효율적이지 않게 됨
(50 50 은 같이 탈 수 있는데 안태웠기 때문ㅠ)
- 함께 타지 못하는 경우에, 반드시 무게가 무거운 사람이 타야한다
--> 절대적인 특징 --> greedy algorithm
Author And Source
이 문제에 관하여(Programers : 구명보트 (greedy)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-구명보트-greedy
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 나의 코드 ] - 효율성 검사 실패
#include <string> #include <vector> #include <algorithm> using namespace std; int solution(vector<int> people, int limit) { int answer = 0, free = limit, tmp; pair<int, int> dif; sort(people.begin(), people.end()); for(int i=0;i<people.size();i++) { /* limit보다 큰 경우는 이미 탄 사람 */ if(people[i] > limit) continue; answer++; free = limit - people[i]; dif = {-1,limit}; /* 같이탈 수 있는 사람들 중, 가장 효율적 탑승이 가능한 사람 찾기 */ for(int j=people.size()-1;j>=0;j--) { tmp = free-people[j]; if(tmp >=0 && dif.second > tmp){ dif = {j, tmp}; break; } } /* 같이 탈 수 있는 사람이 있는 경우 */ if(dif.second < limit) people[dif.first] = limit+1; } return answer; }
- 같이 탈 수 있는 사람과 탔을 때, 가장 여유공간이 적게 남는 경우가 효율적!
- 해당 경우를 찾기 위해 이중 for문을 썼더니 효율성 검사에서 실패함
[ 최적의 코드 ]
#include <string> #include <vector> #include <algorithm> using namespace std; int solution(vector<int> people, int limit) { int answer = 0, head = 0, tail = people.size()-1; /* 오름차순 정렬 */ sort(people.begin(), people.end()); while(head <= tail) { answer++; /* 어차피 한명은 타야하는데, 반드시 무거운 애가 타야함! --> 크기가 작은 애들끼리 있을 때 함께 탈 확률이 크기 때문! (tail-- 필수 / head++ 선택) */ if(people[head] + people[tail--] <= limit) head++; } return answer; }
- 같은 결과를 내지만 정렬 후 head / tail로 접근을 하면 훨~씬 빠르다! (..이런게 알고리즘의 힘인가)
- 주의해야 할 점은 반드시
tail
에 해당하는 사람은 태워야 한다는 것이다!
-> 무게가 적은 사람들 끼리 있을 때 함께 탈 수 있는 경우가 더 발생하기 때문
[50 50 70 80] 일 때 head++를 하면 [50 70 80]이 되어서 효율적이지 않게 됨
(50 50 은 같이 탈 수 있는데 안태웠기 때문ㅠ)
- 함께 타지 못하는 경우에, 반드시 무게가 무거운 사람이 타야한다
--> 절대적인 특징 --> greedy algorithm
Author And Source
이 문제에 관하여(Programers : 구명보트 (greedy)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-구명보트-greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)