[프로그래머스] 구명보트(python)

문제

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

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

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

제한조건

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

 

입출력 예

풀이

이 문제를 처음 보고 접근을 잘못해 '생각보다 쉽게 풀리는거 아닌가?' 라고 생각하고 풀이를 진행했습니다.
문제에는 "구명보트는 작아서 한 번에최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다." 라고 되어있으나, 인원제한이 없는 줄 알고 단순히 정렬 후, 무게를 더해서 제한을 넘게되면 구명보트의 개수가 늘어나는 것으로 이해해 꽤 많은 시간을 버렸습니다....ㅠㅠ

다시 문제로 돌아와서 2명씩 보트를 타야 하는데, 최대한 적은 보트 수를 이용하여 탑승을 할 수 있는 방법을 생각해보니, 아무래도 뒤섞여있는 사람들을 순서대로 2명씩 짝지어서 확인하는 것보다 몸무게 순서로 정렬 후 몸무게가 가장 적은 사람과 가장 많은 사람이 2명씩 짝지어서 확인하는 방법이 보트 수가 가장 적을 것으로 판단하였습니다.
이렇게 조건에 맞게 정리 후 풀이를 진행한 방법은 아래와 같습니다.

1. people 리스트를 정렬한다.
2. start와 end를 리스트의 맨 첫번째와 맨 마지막으로 지정해준다.
3. 두명씩 구출할 수 있는지 확인하기 위해 people[start] + people[end]의 값이 무게 제한을 넘는지를 확인한다.
4. 넘지 않을 경우 적은사람과 많은사람 모두를 탑승시키고, 넘을 경우 몸무게가 많은 사람만을 탑승시킨다.
5. 4번의 조건을 기준으로 3의 과정을 반복한다.


위 풀이를 기준으로 작성한 소스코드는 다음과 같습니다.

def solution(people, limit):
    answer = 0
    people.sort()                # 정렬 후 몸무게 큰 사람과 작은사람 짝지어야 많이 태울 수 있을 것 같음
    start = 0
    end = len(people) -1
    
    while(start<=end):               # 두 명씩 구출해서 다 구출할 때까지 비교
        if(people[start]+people[end] <=limit):  # limit 보다 작거나 같으면 둘다 구출 가능
            start +=1
            end -=1
        else:                     # 안되면 일단 몸무게 큰 사람부터 먼저 구출
            end-=1
        answer +=1
    return answer

그리고 테스트를 진행하면 위의 사진과 같이 모든 테스트를 잘 통과하는 것을 확인할 수 있습니다.