42885. 구명보트

코딩테스트 연습 - 구명보트

문제 유형	난이도	걸린 시간	해결 유무(✅/❌)
탐욕법(그리디)	lv.2	1시간 30분	✅

설계 방법

• 사람들을 몸무게가 무거운 순으로 정렬한다.

• 무거운 몸무게의 사람부터

• 보트의 limit 에서 몸무게를 뺀 만큼을 remainig(남은 무게)에 저장한다.

• 가장 가벼운 사람의 몸무게가 remaining 과 같거나 작다면,

• 가장 가벼운 사람의 몸무게만큼을 remainig에서 빼준다.

• 보트에 remainig 을 push 한다.

• boats에는 사람을 싣고 남은 무게들이 저장되어 있고, 그 길이를 리턴하면 최소구명보트의 개수이다.

코드

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] 로 정렬된다는것을 새롭게 알게 되었다.

참고자료

Array.prototype.sort()