[알고리즘] 프로그래머스 42885 '구명보트' 풀이 _ 파이썬

프로그래머스 42885 구명보트
https://programmers.co.kr/learn/courses/30/lessons/42885
난이도 : 레벨 2
유형 : 그리디 알고리즘

문제

각 구명보트에는 2명까지 탈 수 있고 무게 제한이 있음
구명보트를 최소로 사용하여 모두를 구출하는 문제

풀이

구명보트에는 2명까지만 탈 수 있으므로 최소의 구명보트를 이용하기 위해서는 가장 무거운 사람과 가장 가벼운 사람이 같이 타는 것이 이득이다.

people 배열을 deque로 만든 뒤, 0번째 인덱스와 -1번째 인덱스의 합을 비교해준다.

1. people[0]과 people[1]의 합이 limit보다 작으면 popleft(), pop()
2. 합이 limit보다 크면 무거운 애만 먼저 보낸다. pop()
3. 마지막에 한 명만 남았을 때 고려해주기

정답 코드

from collections import deque

def solution(people, limit):
    answer = 0
    people.sort()
    people = deque(people)

    while people:
        if len(people) == 1:
            answer += 1
            break

        elif people[0] + people[-1] <= limit:
            answer += 1
            people.pop()
            people.popleft()
        else:
            answer += 1
            people.pop()

    return answer