Github

구명보트

1. 개요

2. 문제 설명

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

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

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

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

2-1. 문제 설명 - 제한 사항

  • 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.

  • 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.

  • 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.

  • 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

2-2. 문제 설명 - 입출력 예

people
limit
return

[70, 50, 80, 50]

100

3

[70, 80, 50]

100

3

3. 문제 풀이

function solution(people, limit) {
  // 1) people 배열을 오름차순으로 정렬하기
  people.sort((a, b) => a - b);

  // 2) 구명 보트의 수를 변수로 만들기
  let count = 0;

  while (people.length > 0) {
    // 3) 가장 무거운 사람을 people 배열에서 꺼내오기
    const heavy = people.pop();

    // 4) 가장 무거운 사람과 가장 가벼운 사람의 합이 limit 보다 작으면 맨 앞의 사람(가장 가벼운 사람)을 제거하기
    if (heavy + people[0] <= limit) {
      people.shift();
    }

    // 5) 구명 보트의 수 1올리기
    count++;
  }
  return count;
}

1) people 배열을 오름차순으로 정렬하기

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

people 배열에는 사람의 무게가 요소로 담겨있다. 가장 무거운 사람과 가장 가벼운 사람을 잘 꺼내오기 위해 오름차순으로 정렬한다.

가장 무거운 사람을 Array.pop() 메서드로 꺼내오고 가장 가벼운 사람은 Array.shift() 메서드로 꺼내온다.

2) 구명 보트의 수를 변수로 만들기

let count = 0;

반복문을 통해 count는 증가한다. 추가적으로 반복문에서는 항상 무거운 사람이 하나씩 제거가 되고 조건에 따라서 가장 가벼운 사람도 제거가 될 수 있다.

3) 가장 무거운 사람을 people 배열에서 꺼내오기

const heavy = people.pop();

Array.pop() 메서드를 사용하여 현재 people 배열에서 가장 무거운 사람을 꺼내온다. 꺼내온 값을 heavy 변수에 할당한다.

4) 가장 무거운 사람과 가장 가벼운 사람의 합이 limit 보다 작으면 가장 가벼운 사람을 제거하기

if (heavy + people[0] <= limit) {
  people.shift();
}

한 번의 반복문에서 가장 무거운 사람은 무조건 보트에 타게 되고 만약 현재 people 배열에서의 가장 가벼운 사람의 무게를 더해도 보트의 제한 무게보다 같거나 작다면 함께 탈 수 있다. 함께 타게 될 경우 가장 가벼운 사람은 Array.shift() 메서드를 사용하여 제거한다.

5) 구명 보트의 수 1올리기

count++;

다음 순회로 가기 전 count를 1증가시킨다.

결과

4. Conclusion

Level2같지 않는 어렵지 않았던 문제였다. 다만 보트에 탈 수 있는 사람의 수가 최대 2로 제한이 된다는 조건을 파악하지 못해 두 번의 코드 작성이 있었다. 꼼꼼히 읽지 않고 얼른 코드를 작성하고 싶어 자주하는 실수를 또 하게되었다. 그리고 해당 문제는 그리디 알고리즘으로 풀 수 있다고 한다. 내가 작성한 풀이가 그리디 알고리즘인지 파악을 할 수 없다. 정확한 개념을 모르기 때문인다. 사실 이전에 다른 풀이에서도 그리디 알고리즘을 사용했었을 수도 있다. 개념 공부가 더 필요하다고 느낀 문제였다.

📅 2022-09-28

Previous짝지어 제거하기NextN개의 최소공배수

Last updated