[Python Algorithm] 그리디 알고리즘 - 침몰하는 타이타닉

> 이분 탐색(결정알고리즘) & 그리디 알고리즘 (그리디알고리즘 편)

 

📖 문제 : 침몰하는 타이타닉 

유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 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

n, m = map(int, input().split())
people = list(map(int, input())

people.sort()
cnt = 0

while(people):
    if len(people)==1:
    	cnt+=1
        break
    if people[0]+people[-1] <= m:
    	cnt += 1
        people.pop()
        people.pop(0)
    else:
    	cnt += 1
        people.pop()
	
    
print(cnt)


#근데 여기서 pop(0)을 하게되면, 리스트의 원소들을 다 앞으로 하나씩 땡겨야하기 때문에 비효울적임.

 

# deque 자료구조 사용 !

단순히, list.pop(0)을 하게되면 맨 앞 원소 제거 후 일일이 하나씩 다 땡겨줘야하기 때문에,
deque 자료구조를 사용한다. deque는 list.popleft()을 통해 맨 앞 원소를 제거하면, 맨 앞을 가리키는 포인트 변수가 그 다음 자료를 가르키게 된다. 중간의 자료들은 그대로 두는 것 !

import sys
from collections import deque

n, m = map(int, input().split())
people = list(map(int, input().split()))
people.sort()
people=deque(people)
cnt = 0

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

 

⭐️ Point ! ⭐️

• 반복적으로 pop(0)을 해야하는 경우에는 deque의 popleft()를 사용해봅씨다 ! 
  
  
• 이것도 정렬이지요 !

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이