무인도에 갇힌 사람들을 구하려고 하는데, 사람들의 무게도 다르고 구명보트도 무게제한이 있고 최대 2명 까지 가능하다
사람들 무게 리스트를 받아서 구명보트를 최소한으로 쓸 때, 구명보트 수를 결과값으로 내야하는 문제!
음.. 우선 최대 2명이고, 제한이 있는 구명보트 무게라고 하니.. 두 배열의 원소를 각 곱해서 전체 합이 가장 작은 경우를 구해라는 문제가 생각났다..
결국 무거운 사람 둘을 엮으면 구명보트 제한으로 2개가 나갈것이지만, 무거운 사람 + 가벼운 사람으로 엮으면 1개만으로 가능한 경우가 많을 것..
처음부터 가벼운+가벼운 으로 엮으면 뒤에는 무거운 사람들은 모두 1개씩 타고 나갈지도 모른다..!
그럼 결국 가벼운+무거운 의 짝으로 제한을 체크하고, 안되면 무거운 사람 1개 먼저 타세요! 해야하는 것이다..!!
처음에는 정렬 후 리스트를 그대로 썼는데.. 뭔가 시간상 오류가 떴다..
그래서 뭐가 있을까 하다가 본것이..
"deque" 이다! 양방향 입출이 가능한 큐! collections 에서 임포트 할 수 있다
이게 pop 뿐 아니라 popleft 까지 가능하고, 리스트보다 훨씬 시간적으로 효율이 좋다고 한다..!
그래서~
최종 코드는 이렇다
from collections import deque
def solution(people, limit):
answer=0
people.sort() # 가벼운 사람부터 정렬
dq = deque(people) # deque 로 사용
while dq:
if len(dq)>=2: # 엮을 사람이 있다면
if dq[0]+dq[-1]<=limit:
dq.pop()
dq.popleft()
answer+=1
else:
dq.pop()
answer+=1
else: # 없으면 혼자 가야됨
dq.pop()
answer+=1
return answer
처음엔 가벼운 사람끼리도 엮어보고 하다가 시간 오류로 많이 틀렸다 ㅎㅎ
그래도.. 끝....!