프로그래머스 - 구명보트(파이썬, LV2) / 그리디(Greedy)

https://programmers.co.kr/learn/courses/30/lessons/42885?language=cpp

코딩테스트 연습 - 구명보트

풀이의 핵심은 모든 사람이 보트 1개씩 필요하다고 초기값을 둔다.

그리고 전체 사람들의 무게를 정렬해서

가장 무거운 사람과 가장 가벼운 사람 순으로 같이 갈 수 있는지

같이 갈 수 있을 경우 보트 수를 1개 뺀다(같이 타므로).

 

이런식으로 전체 사람들을 탐색하여 가장 가벼운 사람과 무거운 사람이 만나는 지점에 달하면 탐색을 종료한다.

def solution(people, limit):
    answer = len(people) # 보트 수 초기값 사람 수 만큼
    light_idx, heavy_idx = 0, len(people)-1
    people.sort() # 정렬
    
    while light_idx <  heavy_idx:
        # 가벼운 + 무거운 사람 같이 탈 수 있을 경우
        # 보트 수 하나 빼기
        if people[light_idx] + people[ heavy_idx] <= limit :
            answer -= 1
            light_idx +=1
            heavy_idx -=1
        
        # 같이 못탈 경우 무거운 사람 혼자 보냄
        else :
             heavy_idx -=1
    
    return answer