[Python] [프로그래머스] - 구명보트

 

문제 설명

무인도에 갇힌 사람을 2명씩 구명보트로 구출할 수 있는데 두 명의 몸무게 합이 구명보트가 최대로 구조할 수 있는 무게 이하여야 한다는 제한이 있을 때 필요한 구명보트의 갯수를 구하는 간단한 문제입니다.

 

접근 방법

처음에는 간단히 몸무게 순으로 오름차순 정렬을 하고 앞사람부터 둘씩 짝지어서 구명보트 최대 무게 제한 이하의 몸무게라면 구출을 하는 방향으로 생각했습니다.

예를들어 people = [50, 50, 70, 80] 이면 50kg인 두명을 먼저 구출하고 그다음 차례로 70, 80kg인 사람을 구출하는거죠

But!! 이렇게 하면 people = [5,5,20,20,80,80] 일 경우 구명보트는 4개가 필요하지만 실제로는 3개로도 충분히 구출할 수 있습니다.

20+80을 해서 100kg를 맞추어 구명보트의 최대 몸무게까지 최대한 활용하는거죠 20+80, 20+80, 5+5로 구명보트 3개면 충분합니다.

 

어떻게 코드로 구현할 수 있을까

내림차순으로 먼저 졍렬하고 [80,80,20,20,5,5] 그렇다면 가장 뚱뚱(?)한 사람과 가장 멸치같은(?)사람이 리스트의 양 끝에 오게됩니다. 이사람들끼리 짝을지어 구출하면 구명보트를 최대한 효율적으로 활용할 수 있겠죠

만약 limit보다 두사람의 무게가 크다면 index 0의 사람은 너무 뚱뚱해서(?) 이 사람은 구명보트를 혼자 타야하는 사람이 됩니다.

그래서 혼자 구출을 해주고 남은 사람들끼리 people의 사이즈가 0이 될 때까지 위의 과정을 반복합니다.

리스트 양 끝을 효율적으로 pop하기 위해 deque를 사용했습니다.

 

 

 

내풀이

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    deq = deque(people)

    while deq:
        if len(deq) >= 2 and deq[0] + deq[-1] <= limit :
            deq.popleft()
            deq.pop()
            answer += 1

        else :
            deq.popleft()
            answer +=1
    return answer