https://programmers.co.kr/learn/courses/30/lessons/42885
코딩테스트 연습 - 구명보트
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5
programmers.co.kr
이전에 풀었던 큰수만들기 를 약간은 무식하게 풀고나서 다른사람의 풀이를 보고 뭔가 느낀바가 있다.
뭐라고 말로 표현하기 어려운데 굳이 표현하자면 컴퓨터공학도 처럼 생각하자 는 것이다.
이번 문제를 풀 때 그런 생각으로 임했고 아래와 같이 깔끔하게 풀었다.
만족스러운 깔끔한 코드다.
물론 문제자체도 무척 쉬웠다.
이 문제를 풀기 위해서 우선 문제를 정확히 읽어야한다.
문제의 조건은 한 보트에는 오직 2명만이 탈 수 있고, 제한무게를 초과하면 안된다.
그러므로 이 경우에 가장 그리디스러운, 탐욕스러운 방법은
가장 뚱뚱한놈이랑 가장 홀쭉한놈을 같이 태우는 것이다.
가장 뚱뚱한놈은 가장 왼쪽에 있으므로 popleft 로 꺼내놓고 홀쭉한 놈도 같이 태울 수 있으면 pop 으로 오른쪽 끝도 꺼낸다.
불가능할 경우 가장 뚱뚱한놈만 태운다. 그 이상 탐욕스러운 방법은 없다.
앞, 뒤에서 값을 제거하기에 효율이 좋은 deque 를 사용하였다.
from collections import deque
def solution(people, limit):
answer = 0
people.sort(reverse=True)
d = deque(people)
while d:
max_weight = d.popleft()
if d and max_weight + d[-1] <= limit:
d.pop()
answer += 1
return answer