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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42885

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

기본적인 그리디 문제와 유사해 보인다. 따라서 people을 오름차순으로 정렬한 후, limit에 넘지 않도록 최대한 많은 사람을 태우면 될 것 같다. 하지만 최대 2명 탑승가능 조건이 있기 때문에 앞에서부터 차례로 태우는 것이 아니라 보트에 탄 사람들의 무게가 limit에 최대한 가깝도록 사람들을 태워야 한다. 

 

예시로 people이 [40, 50, 60, 70, 80, 90]로 정렬되어 있는 상태이고 limit은 120이라고 하자.

그러면 앞에서부터 차례로 사람들을 태우는 경우 다음과 같이 5개의 구명보트가 필요하다.

따라서 보트에 탄 사람들의 무게가 limit에 최대한 가깝도록 하기 위해 다음과 같이 low와 high를 설정할 수 있다. 

여기서 people[low]+people[high]가 130이므로 limit 120보다 크다. 따라서 high에 있는 사람은 구명보트를 혼자서밖에 탈 수 없으므로 구명보트 개수를 1 증가시키고 high를 1 감소시켜서 high에 있는 사람을 구명보트에 태워 보낸다. 

갱신된 low와 high상태는 다음과 같다.

여기서는 people[low]+people[high]가 120이므로 limit와 같다. 따라서 low와 high에 있는 사람을 모두 구명보트에 태울 수 있으므로 구명보트 개수를 1 증가시키고 low는 1 증가, high는 1 감소시킨다.

 

이러한 작업을 low <= high일 동안 반복한다.

def solution(people, limit):
    answer = 0
    
    people.sort()
    
    low = 0
    high = len(people) - 1
    
    while low <= high:
        if (people[low] + people[high]) > limit:
            answer += 1
            high -= 1
        elif (people[low] + people[high]) <= limit:
            answer += 1
            low += 1
            high -= 1
    
    return answer