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

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

출처 : 프로그래머스

코딩테스트 연습 - 구명보트

---

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    q = deque(people)
    print(q)
    while q:
        if len(q) == 1: # 혼자면 끝
            answer += 1
            break
        elif q[0] + q[-1] <= limit: # 가장 작은 것, 큰 것을 제거하는게 효율적임
            answer += 1
            q.pop()
            q.popleft()
        else:
            q.pop() # 무거운 사람 먼저 나가기
            answer += 1
    return answer

풀이

어떻게 하면 최소의 보트에 두 명씩 구출할 수 있을지 생각했다.

우선 몸무게가 뒤죽박죽이니 오름차순으로 정렬해서 큐에 넣었다.

가벼운 사람부터 비교하는건 효율적이지 못하다.

가장 무거운 사람과 가장 가벼운 사람 두 명의 몸무게 합이 limit 이하면 최적의 조합이다.

이렇게 해서 큐에서 조건을 만족하면 pop() 한다.

 

2명의 조건이 맞지 않는다면 혼자라도 구명보트에 태워야 하는데,

이때, 무거운 사람부터 구출해야 탐욕적이다.