[ 자바스크립트(JavaScript) ] 프로그래머스 level2 - 구명보트

📍 프로그래머스 2단계 - 구명보트

문제 보기

---

무게 제한이 있는 구명보트를 최대한 적게 사용하여 사람을 태우는 문제인데, 처음에 people을 sort하는 것 까진 생각 했으나, 이후 로직(무게가 적은 순을 먼저 태워야 할지 높은 순을 먼저 태워야 할지?)은 해결하지 못했다. 해결법을 찾아보니 무게가 제일 많은 사람과 무게가 제일 적은 사람을 구명보트에 태우는 방법이 있었다. (왜 이런 생각을 못했을까 😄) 구체적인 로직은 다음과 같다.

 

1. people을 내림차순으로 정렬한다.
2. 무게가 제일 많이 나가는 사람과 무게가 제일 적게 나가는 사람의 합이 limit보다 작다면 둘 다 구명보트에 태운다.
3. 무게가 제일 많이 나가는 사람과 무게가 제일 적게 나가는 사람의 합이 limit보다 크다면 무게가 제일 많이 나가는 사람만 태운다.
4. 무게가 제일 많이 나가는 사람이 limit / 2보다 작다면 구명보트는 남은 인원 수 / 2만큼만 필요하다. 왜냐하면 처음에 people을 내림차순으로 정렬했기 때문에 무게가 제일 많이 나가는 사람 뒤에는 그보다 낮은 무게의 사람밖에 없기 때문이다. 또한 구명보트에는 최대 2명까지만 태울 수 있기 때문이다.

728x90

풀이 방법은 여러 가지가 있지만, 나는 투 포인터를 이용했다. 특이사항으로 9번 라인은 4번 로직의 경우인데, 해당 조건을 만족하게 되면 더 이상 while문을 돌지 않고 return cnt하게 된다. 나머지의 경우에는 공통적으로 lt가 증가하면서 동시에 cnt도 증가한다.

function solution(people, limit) {
  let lt = 0;
  let rt = people.length - 1;
  let cnt = 0;

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

  while (lt <= rt) {
    if (people[lt] <= limit / 2) {
      cnt += Math.ceil((rt - lt + 1) / 2);
      return cnt;
    }

    if (people[lt] + people[rt] <= limit) rt--;
    lt++;
    cnt++;
  }
  return cnt;
}