[프로그래머스] 구명보트 (파이썬)

문제

풀이

그리디 알고리즘에 속하는 문제로 현재 선택할수있는 최선의 선택을 하면 된다. 나는 다음과 같이 접근했다. 

1. people을 오름차순으로 정렬한다.

2. people을 deque 형태로 재정의 한다.

3. people이 비어 있을때까지 아래의 행위를 반복한다.

3-1. people의 가장 큰 몸무게를 가진 사람을 배에 태운다. 즉 people의 가장 끝에 존재하는 사람을 태운다. 그리고 배에 탑승한 사람의 몸무게 정보를 people에서 pop한다.

3-2. 배에 탑승할수 있는 사람들중 몸무게가 가장 낮은 사람을 태운다. 즉 people의 가장 앞에 존재하는 사람을 확인한다. 만약 배에 탑승할수있다면 그 사람의 정보를 people에서 pop한다

3-3. 배의 수를 +1증가시킨다.

 

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

프로그래머스

코드

from collections import deque

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

    while people:
        maximum = people.pop()
        left = limit - maximum
        if people and (left >= people[0]):
            people.popleft()
        
        answer = answer + 1
        
    return answer

 

파이썬의 deque에 대해서 정확히 알게 되었다. 그리고 일단 list형태에서의 pop에 대한 시간 복잡도가 O(N)이기에 주의해야 한다는 것을 알게 되었다.