문제
Lv.2 구명보트
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다
나의 풀이
function solution(people, limit) {
let answer = 0;
people.sort((a,b)=>b-a);
for(let i=0; i<people.length; i++){
if(people[i] + people[people.length-1] <= limit){
answer += 1;
people.splice(i, 1)
people.splice(people.length-1, 1)
i --
}else{
answer += 1;
people.splice(i,1)
i --
};
};
return answer;
};나름 논리적으로 코드를 잘 짰다고 생각했는데 몇시간을 붙잡고 있어도 통과하지 못했다
결국 다른분들이 올려주신 힌트를 참고하여 풀었는데 '어라 나는 왜 이렇게 복잡하게 생각했을까?' 싶었다
그런데 정확성에서는 통과했지만 효율성은 꽝이었다😵💫
수정
function solution(people, limit) {
var answer =0;
people.sort ((a,b) => b-a)
for (var i=0, j= people.length - 1; i <=j ; i++ ) {
if (people[i] + people[j] <= limit ){ // Max + Min 이 제한몸무게 이하이면
j-- // j에서 1씩 빼기 (이전의 인덱스로 넘어가게끔)
answer ++ // 보트 1개 태워보내기
}else{ // Max + Min 이 제한몸무게 초과이면
answer ++ // 보트 1개 태워보내기
};
}; // for문에 의해 people[i]는 다음의 인덱스로 하나씩 전진
return answer;
};우선 내 힘으로 풀어낸 코드는 아니다
효율성을 해결하는 과정에서도 몇시간을 보내다가, 결국 구글링을 통해 많은 코드들을 찾아보았다
가장 깔끔하며 가독성이 좋다고 생각하기도 했지만 새로 배우게 된 점도 있는 코드여서 수정한 코드로 들고왔다
그동안 내가 배웠던 for문은 내부에 1개의 변수만 있었다
그런데 for문 내부에 2개의 변수가 있는 코드는 처음보았다
j를 people.length로 설정함으로써 people 배열의 맨 마지막 요소를 선택하는 것이다
그리고 해당조건에 만족한다면 j--를 통해 중첩된 for문처럼 사용할 수 있었다
이러한 방법을 몰랐다면 나는 계속해서 중첩된 for문을 썼을 것이다
사실 이번 문제는 스스로 풀지 못해 현타가 왔다...
알고리즘 문제 꾸준히 풀면서 사고력을 길러야겠다
+) 여기저기 검색해보다가 shift()는 배열의 맨 앞 원소를 빼고 뒤에 있는 원소들을 앞으로 다 끌고 와야하기 때문에 시간복잡도가 높아서 효율성이 떨어진다는 지식도 습득 완..!
