[Programmers] [탐욕법(Greedy)] [Python] Level2_구명보트

문제

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

프로그래머스

 

풀이

나의 풀이 

# 프로그래머스 2단계 - 그리디 - 구명보트
from collections import deque

def solution(people, limit):
    answer = 0
    people = deque(sorted(people, reverse = True)) # deque 선언

    while len(people) > 1:
        if people[0] + people[-1] <= limit: # 제일 가벼운 사람과 제일 무거운 사람이 같이 탈 경우
            answer += 1
            people.pop() # 가벼운 사람 pop
            people.popleft() # 무거운 사람 popleft
        else: # 무거운 사람 혼자 탈 경우
            answer += 1
            people.popleft()
    if people:
        answer += 1
    
    return answer

 

먼저 구명보트에 최대로 탈 수 있는 사람이 2명이라는 조건이 있다. 

따라서 가장 가벼운 사람과 가장 무거운 사람을 태웠을 때 구명보트를 최소화 할 수 있다.

이를 코드로 구현하면 people[0] + people[-1] <= limit 인데

가장 가벼운 사람과  가장 무거운 사람이 보트에 탔을 때 무게가 limit 보다 크다면 이 보트를 탈 수 없다. 따라서 그 다음 사람은 비교를 하지않아도 되고 가장 무거운 사람은 보트를 혼자 타게되는 것이다. 

또한 

이러한 로직을 바탕으로 구현을 하였다.

 

다른사람의 풀이 

def solution2(people, limit):
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b:
        if people[b] + people[a] <= limit:
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer