프로그래머스(Programmers) : 구명보트 - python 풀이

❓프로그래머스 : 구명보트

📈 문제 요약

한 번에 최대 2명씩 옮길 수 있고 무게 제한이 있는 구명 보트를 활용해 사람들을 구출하려 할 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하면 되는 문제

🤔 접근법

한 번의 시행 착오 후 해결할 수 있었던 문제, 처음에는 힙을 활용해 가장 최소 무게를 가진 사람들부터 짝지어서 구출하는 로직을 작성했다.

우선 가장 최소 무게를 가진 사람을 한 명 보트에 태워 놓고 다음 최소 무게 가진 사람을 태울 수 있으면 태우고 아니면 한 명만 태우는 방식이다. 하지만 이렇게 로직을 작성하면 해결할 수 없는데, 예를들어 [10, 20, 80, 90, 99] 와 같이 사람들이 주어진다면 내가 작성한 로직대로는 (10, 20), (80), (90), (99) 와 같이 4번에 나눠서 구출할 수 있지만 실제는 (10, 90), (20, 80), (99)와 같이 3번에 나눠서 구출하는 것이 정답이다.

이 케이스에서 해결 방법을 생각할 수 있는데, 바로 최소 무게 + 최대 무게 조합으로 사람들을 구출해내는 것이다. 이를 위해 사람들의 무게를 오름차순으로 정렬 후 투포인터를 활용할 수 있다.

하나의 포인터 p1을 인덱스 0에, 두 번째 포인터 p2를 인덱스 len(people)-1에 놓고 만약 두 포인터에 위치한 사람들 두 명을 모두 태울 수 있으면 태우고, 한 명만 태울 수 있다면 p2에 위치한 사람만 태운다.(p1에 위치한 사람만 태워도 무방) 그리고 사람을 태운 쪽의 포인터를 가운데쪽으로 한 칸 이동한다. 이를 p1이 p2를 역전할 때까지 반복하면 필요한 구명보트 수를 최소로 사람들을 모두 태울 수 있다.

🔡 코드

def solution(people, limit):
    people.sort()
    boat = 0
    p1, p2 = 0, len(people)-1
    while p1 <= p2:
        if people[p1]+people[p2] <= limit:
            p1 += 1
            p2 -= 1
        else:
            p2 -= 1
        boat += 1
    return boat