list와 deque

list와 deque에서 pop(0)의 차이점

 

1. pop(0) (list 사용)

• 첫 번째 요소를 제거하면 나머지 요소들의 인덱스를 하나씩 앞으로 이동해야 해서 성능이 저하된다.
• O(n)의 시간 복잡도를 가짐 (리스트가 길수록 더 느려짐)

2. popleft() (deque 사용)

• 첫 번째 요소를 제거해도 나머지 요소들의 인덱스가 유지된다. (재정렬 불필요)
• O(1)의 시간 복잡도를 가짐

 

하나의 보트에 두 사람이 탈 수 있다고 가정할 때 필요한 최소한의 보트 개수를 구해보자.

먼저 승객의 몸무게를 리스트에 저장하고 오름차순으로 정렬한다. 그리고 리스트를 deque로 변환하여 앞뒤에서 빠르게 요소를 제거할 수 있도록 변경한다.

 

가장 무거운 사람과 가장 가벼운 사람이 함께 타기에 너무 무거운 경우(limit을 넘을 경우)

가장 무거운 사람 혼자 탑승한다.

• p.pop()
• cnt+=1

가장 무거운 사람과 가장 가벼운 사람이 함께 탈 수 있다면 둘이 함께 탑승한다. 

• p.pop()
• p.popleft()
• cnt+=1

이 때 조건이 하나 더 추가되는데 

만약에 보트에 타지 못한 (deque or list에 남은) 승객이 하나 있다면 p[0]+p[-1]>limit 라는 조건을 검증할 때 ( 마지막 승객의 몸무게 * 2 ) 하기 때문에 혼자 남은 경우엔 cnt를 하나 증가하고 break로 while문을 종료한다.

 

while p:
    if len(p)==1:
        cnt+=1
        break
    if p[0]+p[-1]>limit:
        p.pop()
        cnt+=1
    else:
        p.popleft()
        p.pop()
        cnt+=1