유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.
< deque >
deque는 import 하여 사용한다.
deque는 스택(후입선출:LIFO)처럼 사용할 수도 있고, 큐(선입선출:FIFO)처럼 사용할 수 있다.
즉, 앞 뒤 양쪽 방향에서 element를 추가하거나 제거할 수 있다.
양끝 element에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, deque는 O(1)로 접근 가능하다.
deque는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.
- 스택 구현 : 오른쪽 끝에서 입출력 / append(), pop()
- 큐 구현 : 왼쪽 입력 오른쪽 출력 / appendleft(), pop(), append(), popleft()
- deque 확장 : 왼쪽 오른쪽 확장 / extendleft(), extend()
- 리스트처럼 사용 : insert(), remove()
- deque 내용 반전 : reverse()
<모범답안>
n, limit = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
p = deque(p) # p를 deque라는 자료구조로 만들기
cnt = 0
while p: # 비어있으면 False
if len(p) == 1:
cnt += 1
break
if p[0] + p[-1] > limit: # 리스트의 마지막 자료는 [-1]
p.pop()
cnt += 1
else:
p.popleft() # deque에서 사용 가능
p.pop()
cnt += 1
print(cnt)sort()를 통해 리스트 p를 오름차순 정렬 한다. 그리고 리스트 p를 deque라는 자료구조로 변환한다.
while p: 라고 쓴 코드는 p가 비어있으면 false가 된다는 것이다. (반복문을 이렇게도 쓸 수 있구나 처음 알았다.)
정렬을 했으므로 맨 왼쪽은 몸무게가 가장 적은, 맨 오른쪽은 몸무게가 가장 많은 사람일 것이다. 따라서 맨 끝 양쪽을 더해가며 제한무게와 비교한다.
p.pop()을 하면 맨 오른쪽 사람이 빠지고, p.popleft()를 하면 맨 왼쪽 사람이 빠진다.
만약 p에 한 명 남았다면 이 한 명은 보트를 탈 수 밖에 없으므로 cnt는 하나 증가하고 반복문이 끝난다.
