Level 2 구명보트 Python3

https://programmers.co.kr/learn/courses/30/lessons/42885?language=python3 

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

 

최종 풀이

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_구명보트.py

hwayeon351/Programmers-Algorithms

 

from collections import deque
def solution(people, limit):
    boat = 0
    people.sort(reverse = True)
    people = deque(people)
    while people:
        max_p = people.popleft()
        if len(people) > 0:
            min_p = people.pop()
            if max_p + min_p > limit:
                people.append(min_p)
        boat += 1
    return boat

---

풀이 과정

풀이 시간 20분

모든 사람들을 구출하는데 필요한 최소의 보트 수를 구하는 문제이다.

가장 몸무게가 많이 나가는 사람과 가장 몸무게가 적게 나가는 사람을 보트에 함께 태울 수 있다면 하나의 보트에 태우고, 아니면 몸무게가 많이 나가는 사람 혼자 보트에 태워나가는 방식으로 문제를 해결하였다.

즉, 아직 구출되지 않은 사람들의 몸무게 리스트 중 가장 큰 몸무게와 가장 작은 몸무게의 합만 보트의 limit과 비교해나가는 방식으로 최적의 해를 구할 수 있으므로 그리디 알고리즘을 적용할 수 있다.

from collections import deque
def solution(people, limit):
    #사용된 보트 수
    boat = 0
    #몸무게가 많이 나가는 순서대로 people을 정렬
    people.sort(reverse = True)
    #가장 큰 몸무게와 가장 작은 몸무게를 pop하기 위해 deque 사용
    people = deque(people)
    #모든 사람이 구출될 때까지 반복
    while people:
        #가장 큰 몸무게를 deque에서 popleft
        max_p = people.popleft()
        #구출할 사람이 더 남아 있는 경우,
        if len(people) > 0:
            #가장 작은 몸무게를 deque에서 pop
            min_p = people.pop()
            #두 사람을 모두 태울 수 없다면 min_p를 다시 deque에 push
            if max_p + min_p > limit:
                people.append(min_p)
        boat += 1
    return boat
#시간복잡도 = O(nlogn), 공간복잡도 = O(n)