🎈 침몰하는 타이타닉(그리디)
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고 있습니다. 구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다.
두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다. 몸무게는 50이상 150이하입니다.
각 승객의 몸무게는 M을 넘지는 않습니다. 즉 탈출을 못하는 경우는 없습니다.
▣ 출력설명
첫째 줄에 구명보트의 최소 개수를 출력합니다.
▣ 입력예제 1
5 140
90 50 70 100 60
▣ 출력예제 1
3
import sys
# sys.stdin = open("input.text", "rt")
N, M = map(int ,input().split())
data = list(map(int ,input().split()))
data.sort()
left = 0
right = N-1
cnt = 0
while left <= right:
if left == right:
cnt += 1
break
if data[left] + data[right] > M:
cnt += 1
right -= 1
else:
cnt += 1
left += 1
right -= 1
print(cnt)🎃 코멘트
무게 제한에 걸리는 경우 안걸리는 경우 나눠서 해결하면 쉽게 가능. (물론 오름차순 정렬 후에 판단)
물론 처음 데이터 마지막 데이터 비교 후에 pop메서드를 통해서 해도 문제없음
근데 리스트로 pop(0)을 하면 맨 앞 자료를 지운 후에 뒤에서 모두 땡기는 연산을 수행한다. 이건 굉장히 비효율적.
-
그렇기에 데크 자료구조를 쓴다면 포인터를 쓰기 때문에 popleft()를 쓰면 떙기는 연산을 하지 않아 효율적으로 활용 가능해 !!!
-
from collections import deque데크 라이브러리 선언 후에 사용하자. -
(deque.popleft(), deque.pop() 을 통해 해결)
