[프로그래머스] 구명보트(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

✔️문제 요약 

1.구명보트에는 최대 2명이 탈 수 있음

2.무게 제한 limit, 사람의 몸무게를 담은 배열 people

3.모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 

 

✔️풀이 방법 

1.Greedy 알고리즘은 당장 눈앞에 있는 것부터 해결하는 알고리즘

2.구명보트에 최대 2명이 탈 수 있는데, 그렇다면 우리는 가벼운 사람과 무거운 사람을 같이 태워야한다. 

- 제일 가벼운 사람과 제일 무거운 사람의 합이 limit를 넘지 않는다면 같이 태우고, 넘으면 무거운애만 태워서 보내버리면 된다 (반복) 

->데큐를 통해서 태워보낼 사람을 버려버리면 빠르게 처리가 가능하다! 

from collections import deque


def solution(people, limit):
    people.sort()
    
    people=deque(people)
    answer=0
    
    while people:
        temp=people.pop()
        answer+=1
        if people and people[0]+temp <= limit:
            people.popleft()
    return answer

 

✔️고찰

-min(people) , max(people)을 쓰기보다는, 내림차순으로 정리한 뒤, 인덱스로 앞뒤를 뽑아버리면 가벼운애와 무거운애가 알아서 찾아진다. 

- 처음에 for문으로 반복문을 돌렸는데, 이 경우 queue가 비어졌을 때 처리가 되지 않아 while문으로 수정하였고, 

아래와 같이 짰었는데, 이렇게 되면 people.pop()이 중복으로 들어가있어서 밖으로 빼도됨 1 

people이 1개만 남았을 떄, people[0] + people[-1]이 작동하지 않음 2 의 문제점이 있어서 위와 같이 코드 수정! 

from collections import deque
import copy 

people=[70, 80, 50]
limit=100


people.sort()

people=deque(people)
cnt=0
for i in copy.deepcopy(people):
    if people:
        if people[0]+people[-1] <=limit: 
            people.pop() 
            people.popleft()
            cnt+=1
        else: 
            people.pop()
            cnt+=1
    else: 
        break
print(cnt)