[프로그래머스] 구명보트 - Python

해당 문제는 탐욕법(Greedy) 방식으로 접근하면 해결할 수 있는 문제다. 

 

단순히 문제를 해결하는 것뿐만 아니라, 효율성도 따져야 하기 때문에 list로 접근하는 것 보다는 deque으로 접근하는 것이 더 편하다. list를 통해 pop(i)를 하게되면 list 내 존재하는 값을 한 번 서칭하고, pop을 하기 때문에 O(n)이 발생하지만, deque을 사용하면 O(1)로 해결이 가능하기 때문이다. 

 

from collections import deque

def solution(people, limit):
    answer = 0 
    deq = deque(sorted(people))
    
    while len(deq) > 1:
        if deq[0] + deq[-1] > limit:
            deq.pop()
            answer += 1
        else:
            deq.pop()
            deq.popleft()
            answer += 1
    if deq:
        answer += 1
    
    return answer

deque[0]과 deque[-1]을 더한 값과 limit을 비교하고, 만약 더 크다면 deque[-1]을 pop하는 형태로 처리할 수 있다. 마지막으로는 deque이 0이면 바로 return 하고 deque 안에 값이 존재하면 +1을 하면 된다.