프로그래머스(programmers) 구명보트 python 정답 [Greedy Algorithm]

프로그래머스(programmers) 구명보트 python 정답 [Greedy Algorithm]

문제 링크

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

프로그래머스

---

문제 정답

입출력 예시

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

정답 코드

from collections import deque
def solution(people, limit):
    q = deque(sorted(people))
    answer = 0
    while q:
        if len(q) >=2 and q[0] + q[-1]<=limit:
            q.popleft(),q.pop()            
        else:
            q.pop()
        answer +=1            
    return answer

---

문제 해설

한 개의 보트에 최대한 많은 무게를 실어 보내야 한다.

그런데 최대 2명 까지밖에 태울 수 업다고 한다.

떠러서 가장 무거운 사람과 가벼운 사람을 같이 보낼 수 있는지 테스트하면 될 것이다.

만약 가장 가벼운 사람과도 무거운 사람을 같이 보낼 수 없다면,

무거운 사람만 태워보내면 된다.

 

시간 복잡도는 정렬 알고리즘의 O(nlogn)이 될 것이다.

while 반복문은 n개만 순회하면 끝난다.