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

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

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

문제유형 : 그리디, 투포인터 

 

문제풀이 : 가능한 최대한 많이 담아서 보내야하므로 그리디 

• 나는 큐를 이용해서 풀었다. ( 투포인터 느낌 )
• 내림차순 정렬한 큐에서 왼쪽, 즉 가장 큰값부터 (popleft) 보트에 태우고, 더이상 큰값을 태울수 없을때
  • 큐의 오른쪽, 즉 가장 작은값부터(pop) 보트에 태워서 한번 보낼때 가장큰애들과 가장작은애들의 조합으로 보낼수있는 최대를 보내도록 했다.
• 효율성 검사를 위해서 리스트를 한번만 순회하는것이 좋을것이라고 생각해서 앞에서 전진, 뒤에서 전진하는 느낌으로 풀었다.
• 다른분 풀이를 보니 투포인터로 푸는분도 계셨다. 어쨋든 포인트는 한번만 순회해서 O(n)시간에 풀어야한다는점 

 

정답코드:

from collections import deque
def solution(people, limit):
    answer = 0
    #가장 큰숫자로 소팅하고 아래로 내려가면서 합이 limit이하인지점까지 끊는다.
    people.sort(reverse=True)
    q = deque(people)
    weight_sum = 0
    boat = 0
    while q:
        max_ = q[0]
        if weight_sum + max_ <= limit: # 이사람을 태울수 있는가? 가설을 검증
            weight_sum += q.popleft()
        else: #더이상 못태워요~
            while True:   # 가벼운 애들을 태울수있는만큼 태운다.
                min_ = q[-1] 
                if weight_sum + min_ <= limit:
                    weight_sum += q.pop()
                else:
                    break
            boat += 1
            weight_sum = 0
    
    return boat+1