그리디알고리즘 - 4. 침몰하는 타이타닉

나의 풀이

내림차순 정렬하고

제일 큰 무게(인덱스 : 0 ) 와 제일 작은 무게(인덱스 : -1 ) 를 더한 값이
무게제한 m 을 넘는다면
제일 큰 무게를 갖는 인원은 혼자 타야함 ( pop(0) )

---

강의 풀이

만약 리스트에 한명만 남아 있을 때

if arr[0]+arr[-1] > limit:   # 1명만 타고 갈 경우
        arr.pop()
        cnt += 1

arr[0] + arr[-1]   —>  같은 값을 더하기 때문에 논리적 오류가 발생한다

else:                     # 2명이 타고 갈 경우
        arr.pop(0)
        arr.pop()
        cnt += 1

리스트에 하나 남아있는 값을 pop(0) 하고
그 다음 pop() 을 하면 오류가 발생

리스트의 pop(0) 연산

리스트의 pop(0) 연산시 뒤의 자료들이 앞으로 당겨지는 연산
—> 매우 비효율적이다

list의 경우 pop()으로 마지막 값을 꺼내는 경우 O(1) (일정한 시간) 시간이 걸리는데,
pop(0)으로 가장 앞단에 값을 꺼낼때는 list 크기에 따라 읽어 오는 시간이 달라진다.
O(n) 시간이 걸린다.

덱(Deque) , 양방향 삭제/삽입 가능

하지만 deque를 사용할 경우 popleft()를 사용하면
리스트의 pop(0)과 같은 기능을 주면서 걸리는 시간은 O(1)이 걸린다.



덱(Deque) 자료구조 사용

from collections import deque

arr = deque(arr)

arr.popleft()  #pop(0) 과 같음 
arr.pop()