문제 링크

분류 / 레벨 / 언어

탐욕법(Greedy) / LV.2 / Javscript

설명

그리디 알고리즘에서 우선순위로 둘 만한것 = 처리하기 쉬운 요소, 놔두면 피곤해지는 요소
이 문제에서는 비교적 무거운 사람을 우선순위로 둘 만하다.

오름차순으로 정렬하여,
pop()한 사람을 먼저 태우고, 그 위에 가벼운 사람을 가능한 실어서 출발시킬 것이다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function solution(people, limit) {
  let boat = 0;
  let sum = 0;

  people.sort((a, b) => a - b);

  while (people.length > 0) {
    if (sum === 0) {
      boat++;
      sum += people.pop();
    } else {
      while (sum < limit) {
        if (people[0] && sum + people[0] <= limit) sum += people.shift();
        else break;
      }
      sum = 0;
    }
  }
  return boat;
}