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

Solution:

from collections import deque
def solution(people, limit):
    
    # 초기화
    people.sort()
    q=deque(people)
    cnt=0
    
    # 사람들이 2명 이상 있어야함.
    while len(q)>=2:
        heavy = q.pop()
        # 가벼운 사람 + 무거운 사람
        if q[0]+heavy<=limit:   
            # if q:
            q.popleft()
            cnt+=1
        else:
            cnt+=1

    if q:
        return cnt+1
    
    return cnt

 

 

Skills:

1. deuqe는 pop(), popleft() 둘다 있음, 시간복잡도 둘다 O(1) 상수시간임.
2. 큐에서, q[0],q[-1]의 시간복잡도는 O(1) 상수시간임. (선형시간아님), but 0, -1 이 아니라면 O(n) 선형시간임.