[프로그래머스 LV.2] 구명보트 python 풀이 (feat.그리디)

구명보트 문제 풀이 with 그리디 

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

프로그래머스

 

 

 

 

문제 풀이 

 

내 코드 !

def solution(people, limit):
    #최대 두명 탑승 가능
    ans=0
    people.sort()
    left=0 #가장 가벼운 사람 
    right=len(people)-1 #가장 무거운 사람의 인덱스
    while left<=right:
        if people[left]+people[right]<=limit:
            left+=1
        right-=1
        ans+=1

    return ans

 

문제풀이 생각할점 

처음에는 오름 차순한다음에 몸무게가 제일 적은 사람부터 태울 생각을 했는데 이렇게 풀면 비효율적이라는 생각이 들었다. 그게 효율적이라고 생각했는데, 가벼운 사람들끼리 먼저 태우면 나머지 무거운 사람들을 혼자 태우게 되어 보트 수가 증가할 가능성이 높았다. 

 

무거운 사람 우선 처리

그래서 무거운 사람은 추가로 누군가와 함께 태우기 어렵기 때문에 가능한 빨리 처리해야 보트의 수를 줄일 수 있다.

 

 

그리디 알고리즘

무거운 사람을 한 번에 처리하고, 그 사람과 가벼운 사람을 태울 수 있는지 확인하는 방식으로 문제 풀기

1)오름 차순 정렬 후 

2)가벼운 사람과 무거운 사람 효과적으로 매칭

3)무조건 무거운 사람은 태우는거임 , 조건을 만족하면 가벼운 사람도 태우는거 ! 

 

그래서 이에 해당할때, 보트 수를 +1해주면 최적의 보트 수를 구할 수 있다.

 

 

끗!