구명보트 (level 2)

원용현·2022년 10월 16일

알고리즘

프로그래머스

목록 보기

29/49

링크

https://school.programmers.co.kr/learn/courses/30/lessons/42885

문제

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

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

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

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

문제 이해

탐욕 알고리즘을 적용하여 문제를 해결한다.

구명보트에 최대 2명씩 타는 것이 가능하기 때문에 2명이 탈 수 있는 경우와 혼자 타야하는 경우를 구분지어야한다.

사람들의 무게를 가지고 있는 배열을 정렬하여 최소 무게를 가진 사람과 최대 무게를 가지고 있는 사람이 함께 하나의 구명보트에 탈 수 있는지를 확인한다. 그 결과 두 사람이 함께 탈 수 있다면 전체 구명보트의 수는 하나가 증가할 것이다.

함께 탈 수 없다면 최대 무게를 가진 사람을 하나의 보트에 태우고 그 다음 최대 무게를 가진 사람과 최소 무게를 가진 사람을 함께 태울 수 있는지 비교한다.

배열을 정렬한다.

가장 가벼운 사람과 가장 무거운 사람의 무게 합계를 보트 무게 한계와 비교한다.
2-1. 비교 결과 한계를 넘으면 가장 무거운 사람을 혼자 보트에 태운다.
2-2. 비교 결과 한계를 넘지않으면 두 사람을 함께 보트에 태운다.

2의 과정을 모든 사람이 모두 보트에 탑승할 때까지 반복한다.

코드

function solution(people, limit) {
    let result = 0
    let head = 0
    let tail = people.length - 1
    
    people.sort((a, b) => b - a)
    
    while(true) {
        if(people[head] + people[tail] <= limit) {
            head++
            tail--
        } else {
            head++
        }
        
        result++
        
        if(head > tail) return result
        else if(head === tail) return result + 1
    }
}