TIL 05 [프로그래머스]구명보트 JS

문제

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

1.최대 2명씩 탈 수 있다.
2.무게제한이 있다. 무게제한 이하 까지만 탈 수 있음.
3.구명보트를 최대한 적게 사용.

제일 무거운 사람과 제일 가벼운 사람을 함께 태워야겠다 라고 생각.
사람들을 몸무게가 많은순으로 정렬한 후 제일 무거운사람과 가벼운사람이 함께 보트에탈 수 있으면 태워버리고, 아닌경우 제일 무거운사람만 태운다.

제일무거운 사람순으로 보트를 태워서 보내면 제한무게의반인 값보다 작은 몸무게가 나오면 무조건 두명이 탈 수 있으므로, 그때의 people 배열의 길이를 /2 해서 answer에 더해주면 된다고 생각했다.

function solution(people, limit) {
  let answer = 0;

  const sortedPeople = people.sort((a, b) => {
    return b - a;
  });

  while (sortedPeople.length > 0) {
    if (sortedPeople[0] <= limit / 2) {
      answer += Math.ceil(sortedPeople.length / 2);
      break;
    }
    answer++;
    if (sortedPeople[0] + sortedPeople[sortedPeople.length - 1] <= limit) {
      sortedPeople.shift();
      sortedPeople.pop();
    } else {
      sortedPeople.shift();
    }
  }

  return answer;
}

이 경우 효율성 테스트에서 시간초과로 실패를 하게된다.
shift가 배열의 인덱스0인 부분을 제거하는 거기 때문에 나머지 요소들도 수정을 해줘야해서 성능이 좋지 않다는게기억이 났다.

📚모던자바스크립트
shift 메서드를 호출한 것과 동일한 효과를 보려면 인덱스가 0인 요소를 제거하는 것만으론 충분하지 않습니다. 제거 대상이 아닌 나머지 요소들의 인덱스를 수정해 줘야 하죠.

shift 를 사용하지 않으려고 배열은 그대로 두고.
배열의 인덱스 값을 이용 ->
제일 첫 배열 first , 배열의 제일 뒤(second)에서부터 while문을 돈다.

function solution(people, limit) {
  let answer = 0;

  const sortedPeople = people.sort((a, b) => {
    return b - a;
  });
  let first = 0;
  let second = sortedPeople.length -1
  while (first<=second) {
    answer++;
    
    if (sortedPeople[first] + sortedPeople[second] <= limit) {
      first ++;
      second --;
    } else {
        first ++;
    }
  }
 
  return answer;
}

확실히 빨라진 속도를 볼 수있다.

다른사람의 코드

for문에서 i와 j 를 한번에 선언해주고 구명보트에 함께 탈수있을때 조건에만 j만 마이너스 해주는 식으로 하니까 훨씬 깔끔했다.

function solution(people, limit) {
  let answer = 0;
  people.sort((a, b) => {
    return b - a;
  });

  for (let i = 0, j = people.length - 1; i <= j; i++) {
    answer++;
    if (people[i] + people[j] <= limit) j--;
  }
  return answer;
}

정리

그리디 알고리즘 kit에 있는 문제를 풀어보니까.
그 순간의 최적의해. 제한적인 선택지가 있을때 (최대 2명) 프로그래머스 체육복 문제처럼 앞,뒤 사람에게만 ,이런 제한적인 순간에서의 최적의해가 전체적으로 봤을때 최적의 해가 되는거 같다.