[JS] 구명 보트

처음에 문제를 잘못 읽어서 푸는데 애먹었던 문제였다.

 

 

 

최소한의 구명보트를 찾는데 어떻게 그리디로 해결할 수 있지? 끙끙대면서 문제를 읽어보니 구명보트에서는 최대 2명씩만 탈 수 있다는 조건이 붙어있는 문제였다.

 

아..

 

 

 

우선 배열을 정렬하고,

 

 

즉, 가장 무거운사람과 가장 가벼운 사람을 비교해서 탈 수 있다면 둘을 태워보내고, 그렇지 않으면 무거운사람만 보내는 식으로 문제를 해결하면 된다!

 

 

이때 가장 가벼운 사람을 shift를 사용해서 꺼내면 시간복잡도가 늘어나니 인덱스를 활용해서 해결했다.

 

 

 

function solution(people, limit) {
  people.sort((a, b) => a - b);
  let ret = 0;
  let i = 0
    
  while (people.length-i > 0) {
    let p = people.pop();
    while (p < limit && people.length-i > 0) {
      if (p + people[people.length - 1] <= limit) {
        p += people.pop();
      } else if (p + people[i] <= limit) {
        p += people[i++]
      } else break;
    }
    ret++;
  }

  return ret;
}