https://programmers.co.kr/learn/courses/30/lessons/42885?language=javascript
그리디 알고리즘에 속하는 문제이고
접근 방식도 어렵지 않았지만,, 효율성에서 헤매서 기록해본다
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
가 핵심이다.
어떻게 하면 구명보트를 최대한 적게 사용할 수 있을까??
-> 구명보트의 limit 만큼을 최대한 꽉 채워서 운반해야지 최대한 적게 사용할 수 있다.
-> 제일 무거운사람과 제일 가벼운 사람을 조합하는것이 구명보트를 꽉 채우는 방법이다.
-> 그러기 위해 내림차순으로 조합한후 양끝값(가장무거운사람, 가장가벼운사람)을 더해서 limit보다 작으면 옮기면되고, 아닐때에는 맨 앞 값(가장 무거운사람)만 넣어서 옮긴다!
function solution(people, limit) {
var answer = 0;
people.sort((a,b)=>b-a); // 내림차순 정렬
while(people.length!==0){
let fat=people.shift();
let skinny=people[people.length-1];
answer++;
if(fat+skinny<=limit){
people.pop();
}
}
return answer;
}
위의 코드로 하면 효율성에서 실패된다 ㅠ.ㅠ
O(n) 시간복잡도를 가지는 shift() 메소드를 제거하고
for문을 사용하여 인덱스 범위를 좁히는 방법으로 개선하였다.
function solution(people, limit) {
let answer=0;
people.sort((a,b)=>b-a);
let peopleCnt=people.length;
for(let i=0;i<peopleCnt;i++){
if(people[i]+people[peopleCnt-1]<=limit){
peopleCnt--;
}
answer++;
}
return answer;
}