프로그래머스 Lv.2 - 구명보트[Python]

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

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

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

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

제한사항

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

입출력 예peoplelimitreturn

[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

---

나의 풀이

def solution(people, limit):

    people.sort()
    # 시작, 끝 인덱스
    start, end = 0, len(people)-1
    # 보트의 수
    count = 0
    while start <= end:
        # 보트의 수 증가
        count += 1
# 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나
        if (people[start] + people[end] <= limit):
            start += 1
            end -= 1

# 한 명(몸무게가 가장 많은 사람)을 태우기 
        else:
            end -= 1
    return count

 

1. 핵심은 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 계속해서 매칭시켜서 최대한 한번에 태워보내주면 최소값을 찾아줄 수 있다.
2. 먼저 people의 list를 정렬을 해주어야한다. 이후 가장 몸무게가 큰 사람과 가장 작은 사람의 무게를 더해 limit와 비교한 뒤, 작으면 둘다 태우고(두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나), 크다면 몸무게가 가장 큰 사람만 태운다.(한 명(몸무게가 가장 많은 사람)을 태운다.)

투 포인토 알고리즘을 사용해 풀어 보았다.

---

Greedy (탐욕법, 탐욕 알고리즘)

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

위의 그림에서는 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 큰 수는 99이다. 이처럼 전체 문제해결에서의 최적 해답을 찾지는 못한다.

하지만 이러한 단점들을 극복하는 Greedy의 가장 큰 장점은 계산 속도에 있다. 그래서 Greedy 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

투 포인터 (Two Pointer)

• 배열 안에 있는 값들을 연속해서 더하거나 연산하는 경우에 사용 인덱스를 가리키는 두 개의 변수(포인터)를 선언하여 사용하는 특징이 있어 투 포인터라 불림
• 예를 들어 N개의 숫자가 들어있는 배열이 주어질 때, 부분 집합의 합이 특정 숫자인 M인 경우의 수를 구하는 문제에 적용한다면, 배열의 인덱스를 가리키는 startPointer와 endPointer를 생성한 후 특정 규칙에 의해 각 포인터를 움직여 배열을 탐색해 문제를 해결할 수 있으며, 그 규칙은 다음과 같습니다.1-2) 만약 startPointer의 값이 배열의 길이와 같을 경우 탐색을 종료합니다.2) 위의 세 규칙 중 해당하는 연산이 끝난 후 만약 현재까지의 합이 M과 같다면 답을 +1증가 시킵니다.
• 1-3) 나머지 경우(현재까지의 합이 M보다 작을 경우)에는 합에 startPointer가 가리키고 있는 값을 더한 후 startPointer를 +1 증가시킵니다.
• 1-1) 현재까지의 합이 M보다 크거나 같은 경우 합에서 endPoiner가 가리키고 있는 값을 뺀 후 endPointer를 +1 증가시킵니다.
• 투 포인터를 사용한다면 한 번 답이 될 수 없다고 판명된 이후의 값들을 더 이상 탐색하지 않으므로 시간 복잡도가 O(n)이 되어 완전 탐색에 비해 효율이 훨씬 좋음