[프로그래머스] 탐욕법 - 구명보트 문제 풀이

오늘은 프로그래머서에서 탐욕법 문제 중 구명보트 문제 풀이를 해보겠습니다. 구명보트의 제목으로 어떤 문제가 나올지 정말 궁금합니다. 탐욕법 문제 난이도 2단계 마지막 문제입니다. 그럼 문제 풀이 시작해보겠습니다.

 

 

프로그래머스 > 탐욕법 > 구명보트 문제 풀이

 

 

 

 

▒ 문제 정보

• 문제명: 구명보트
• 문제 난이도: Level 2
• 문제 푼 사람 수: 15433명
• 사용 가능 언어: 4개 (JavaScript 사용)

 

이번 문제의 사용 가능 언어가 4개로 정말 적습니다. 그 중에 저의 주 언어인 JavaScript가 있다는게 너무 좋네요~

 

 

 

 

▒ 문제 설명

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

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

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

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

 

 

역시 구명보트는 무인도에서 사람 구하는 방법으로 문제가 나왔습니다. 그럼 문제 설명을 정리해보겠습니다.

 

• 모든 사람(people)을 구하기 위한 구명보트의 개수 최소값 구하기
• Inputs
  • people: 사람들의 몸무게를 담은 배열(Array<number>)
  • limit: 구명보트의 제한 무게
• Output: 모든 사람을 구하기 위한 구명보트의 최소 개수

문제에서 주어진 주요한 제한사항이 하나 있습니다. 구명보트에 탈 수 있는 인원의 최대는 2명이라는 점입니다.

 

 

 

 

▒ 제한 사항

⊙ 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
⊙ 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
⊙ 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
⊙ 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

 

• 1 ≤ 사람 수(N) ≤ 50,000
• 40 ≤ 몸무게 ≤ 240
• 40 ≤ 구명보트 제한 무게 ≤ 240
• 구명보트의 무게 제한 ≤ 사람들의 몸무게 최댓값

 

 

 

 

▒ 입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

 

이번 문제는 입출력 예에 대한 설명이 없으므로, 간단하게 직접 작성해보겠습니다.

• 예제 #1
  • 사람들을 70kg 1개, 50kg + 50kg 1개, 80kg 1개로 총 3개의 구명보트로 구출할 수 있으므로 3개.
• 예제 #2
  • 사람들을 70kg 1개, 50kg 1개, 80kg 1개로 총 3개의 구명보트로 구출할 수 있으므로 3개.

 

 

 

 

▒ 알고리즘 만들기

1.  사람들을 몸무게 순으로 정렬한다.
2. 모든 사람은 하나의 구명보트에 타있다고 가정한다.
3. 맨 앞과 맨 뒤 사람부터 선택해서 선택된 두 사람의 몸무게 합이 제한 무게보다 큰지 확인한다.
   3-1. 크다면, 뒤에서 앞으로 이동하여 사람을 선택한다.
   3-2. 작거나 같다면, 이 두 사람은 한 배에 태울 수 있기에 구명보트 하나를 제거한다.
          앞에서 뒤로 이동하여, 뒤에서 앞으로 이동하여 각각 사람을 선택한다.
4. 3번을 모두 확인하였을 때 제거된 구명보트를 뺀만큼 반환한다.

 

 

이 문제의 알고리즘에서 키포인트는 먼저 순서대로 정렬 후, 맨 앞과 맨 뒤에서 가운데로 이동하면서 비교하는 것입니다. 즉, 한번 확인될 때마다 2번씩 확인되므로 정렬을 제외한 비교 알고리즘에서 logN의 시간복잡도를 가질 수 있습니다.

 

 

 

 

▒ 코드 구현

function solution(people, limit) {
    let startIndex = 0;
    let endIndex = people.length - 1;
    // 1.  사람들을 몸무게 순으로 정렬한다.
    people.sort((a, b) => a - b);
    
    // 2. 모든 사람은 하나의 구명보트에 타있다고 가정한다.
    let answer = people.length;
    
    // 3. 맨 앞과 맨 뒤 사람부터 선택해서 선택된 두 사람의 몸무게 합이 제한 무게보다 큰지 확인한다.
    while(startIndex < endIndex) {
        // 3-1. 크다면, 뒤에서 앞으로 이동하여 사람을 선택한다.
        if(people[startIndex] + people[endIndex] > limit) {
            endIndex--;
        } else {
            // 3-2. 작거나 같다면, 이 두 사람은 한 배에 태울 수 있기에 구명보트 하나를 제거한다.
            //      앞에서 뒤로 이동하여, 뒤에서 앞으로 이동하여 각각 사람을 선택한다.
            startIndex++;
            endIndex--;
            answer--; 
        }
    }
    // 4. 3번을 모두 확인하였을 때 제거된 구명보트를 뺀만큼 반환한다.
    return answer;
}

 

 

 

 

▒ 채점 결과

 

 

이번 문제는 N이 최대 50,000이었데 효율성 테스트 케이스가 5개나 됩니다. 그만큼 알고리즘의 복잡도 및 모두 탐색해서 결과를 도출해야하는 그리드한 알고리즘으로 코드를 구현해야하는 만큼 효율성을 고려해야 했습니다.

구명보트 문제 풀이는 정확성 테스트 케이스 15개, 효율성 테스트 케이스 5개를 모두 통과하여 100점으로 문제 풀이를 마치겠습니다.