[프로그래머스] 구멍보트 문제풀이(파이썬/python/그리디/greedy)

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 

구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

 

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

 

 

 

문제 풀이

<그리디 알고리즘 - 투 포인터 알고리즘>

아무리 생각해도 배열을 두 번은 확인해야 하는 방법밖에 생각을 못하겠어서

질문하기를 보고 힌트를 얻었습니다.

 

그리디로 해결하기 위해서 투 포인터 알고리즘을 사용합니다.

투 포인터 알고리즘은 두개의 포인터를 사용하는 탐색 기법입니다.

 

예를 들어 정렬된 배열에서 어떤 쌍을 검색할 때

배열이 정렬되어 있는 상태에서 양극단에 두 개의 포인터를 두고

조건부로 두 포인터를 배열에서 이동하면서 탐색합니다.

 

(또는 두개의 포인터를 같은 시작점에서 사용 가능)

 

<적용하기>

구명보트 문제에 적용하는 방법은

 

우선 입력받은 사람들 몸무게 배열을 정렬합니다.

 

양 극단에 있는 값인 최솟값(왼쪽 포인터)과 최댓값(오른쪽 포인터)으로 시작하여 

만약 이 두 값을 더했을 때  무게 제한보다 작다면

구명보트를 함께 탈 수 있기 때문에

왼쪽 포인터는 +1 오른쪽 포인터는 -1해 주고

만약 더한 값이 무게 제한을 넘어간다면

오른쪽 포인터의 값은 다른 어떤 값과 더해도 무게 제한을 넘을 것이기 때문에 하나의 보트를 사용해야 하므로

오른쪽 포인터 값은 -1해 주고 결과를+1해 줍니다.

 

아래는 파이썬으로 구현한 코드입니다.

while문을 통해 구명조끼에 같이 탈 수 있는 사람 쌍을 찾습니다.

왼쪽 인덱스 값이 오른쪽보다 커진다면

이는 모든 배열의 요소를 확인한 것이므로 반복을 멈춥니다.

 

Python 코드

 

def solution(people, limit):
    answer = 0
    left = 0
    right = len(people)-1
    people.sort()
    while left <= right:
        if people[left]+people[right] <=limit:
            left +=1
            right -=1
            answer+=1
        else:
            right-=1
            answer+=1

    return answer

 

 

<오늘의 교훈>

새로운 기법을 다른 문제에서도 적용할 수 있도록 잘 이해하고 기억해두어야겠다.