프로그래머스[Level 2] 구명보트 (그리디)

문제

제한 사항

입출력 예

풀이

function solution(people, limit) {
  let answer = 0;
  people.sort((a, b) => a - b);
  let lt = 0;
  let rt = people.length - 1;
  while (lt <= rt) {
    if (people[lt] + people[rt] <= limit) {
      lt++;
      rt--;
    } else {
      rt--;
    }
    answer++;
  }

  return answer;
}

대표적인 그리디 문제이다.

이 문제는 실제처럼 설명을 하면 훨씬 이해가 잘 된다.

무게를 오름차순으로 정렬하고, 가장 가벼운 사람과 무거운 사람을 보트에 태운다.
두사람의 무게가 보트의 제한을 넘지 않는다면 태워서 내보낸다.
보트의 제한을 넘는다면, 무거운 사람만 태워서 내보낸다.

어차피 그의 짝이었던 사람은 남은 사람 중 가장 가벼운 사람이었기에 그냥 내보낼 수 밖에 없다.

이해가 훨씬 잘 된다.