Younho9 NotesProgrammers 42885. 구명보트
Title
Programmers 42885. 구명보트
Category
AlgorithmTags
Aliases
Programmers 42885. 구명보트Created
3 years ago
Updated
last year
| 문제 유형 | 난이도 | 걸린 시간 | 해결 유무(✅/❌) |
|---|---|---|---|
| 탐욕법(그리디) | lv.2 | 1시간 30분 | ✅ |
설계 방법
사람들을 몸무게가 무거운 순으로 정렬한다.
무거운 몸무게의 사람부터
보트의
limit에서 몸무게를 뺀 만큼을remainig(남은 무게)에 저장한다.가장 가벼운 사람의 몸무게가
remaining과 같거나 작다면,가장 가벼운 사람의 몸무게만큼을
remainig에서 빼준다.보트에
remainig을 push 한다.boats에는 사람을 싣고 남은 무게들이 저장되어 있고, 그 길이를 리턴하면 최소구명보트의 개수이다.
코드
javascript
function solution(people, limit) {
const boats = [];
people
.sort((a, b) => b - a)
.forEach((heavyPerson) => {
let remaining = limit - heavyPerson;
if (people[people.length - 1] <= remaining) {
remaining -= people.pop();
}
boats.push(remaining);
});
return boats.length;
}
function solution(people, limit) {
const boats = [];
people
.sort((a, b) => b - a)
.forEach((heavyPerson) => {
let remaining = limit - heavyPerson;
if (people[people.length - 1] <= remaining) {
remaining -= people.pop();
}
boats.push(remaining);
});
return boats.length;
}
시간 복잡도
sort : O(NlogN)
순회 : O(N)
-> O(NlogN)
어려웠던 점
문제를 처음에 제대로 읽지 않아서, 보트에 사람 수 제한은 없고, 무게 제한만 있는줄 알았다.
문제 해결 방법을 찾는 것이 쉽지 않았다.
정렬을 하는 것이 중요했는데, 이를 떠올리기 어려웠다.
sort().revers() 로 숫자를 내림차순으로 정렬할 수 있는 것으로 기대했는데, sort()가 유니코드 순으로 정렬하여, [1, 2, 10]의 경우 [1, 10, 2] 로 정렬된다는것을 새롭게 알게 되었다.