프로그래머스 구명보트 풀이: 정렬과 양끝 투 포인터 그리디

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 구명보트
• 학습: 그리디 알고리즘 학습 가이드
• 출처: 프로그래머스 코딩테스트 고득점 Kit, 탐욕법
• 자체 판단 난이도: Level 2

먼저 몸무게를 순서대로 정렬한 뒤, 가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있는지 확인하면 된다. 두 사람의 합이 제한을 넘으면 무거운 사람을 혼자 태우고, 넘지 않으면 두 사람을 함께 태우는 규칙을 반복한다. 정렬과 양끝에서 이동하는 포인터를 함께 사용해야 하지만, 매번 무엇을 선택할지가 명확하므로 Level 2로 판단한다.

1. 문제 요약

사람들의 몸무게가 people 배열로 주어지고, 구명보트 한 대가 운반할 수 있는 무게의 최댓값 limit이 주어진다. 모든 사람이 탈출하기 위해 필요한 구명보트의 최소 개수를 반환한다.

구명보트 한 대에는 최대 두 명만 탈 수 있다. 따라서 두 사람의 몸무게 합이 limit 이하일 때만 함께 태울 수 있다.

• people의 길이는 1 이상 50,000 이하다.
• 각 사람의 몸무게는 40 이상 240 이하다.
• limit은 40 이상 240 이하다.
• 모든 사람을 태울 수 있는 입력이 주어진다.

보트 수를 줄이려면 가능한 한 두 명씩 태워야 한다. 하지만 아무 두 사람이나 묶으면 무거운 사람끼리 한 보트를 만들 수 없어 오히려 보트를 낭비할 수 있으므로, 어떤 순서로 짝을 정할지 결정해야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그리디 선택 기준

사람들을 몸무게 오름차순으로 정렬하고, 가장 가벼운 사람을 가리키는 left와 가장 무거운 사람을 가리키는 right를 둔다.

매번 가장 무거운 사람은 반드시 이번 보트에 태운다. 그 사람을 다른 사람과 태울 수 있다면 가장 가벼운 사람과 짝을 짓는다.

• people[left] + people[right] <= limit: 두 사람을 함께 태우고 left, right를 모두 이동한다.
• 합이 limit보다 큼: 가장 무거운 사람은 누구와도 함께 탈 수 없으므로 혼자 태우고 right만 이동한다.

두 경우 모두 보트 하나를 사용하므로 boats를 증가시킨다. left > right가 되면 모든 사람을 처리한 것이다.

가장 무거운 사람의 동행 여부만 보면 되는 이유

현재 가장 무거운 사람을 다른 사람과 태울 수 있는지가 남은 문제의 핵심이다. 가장 가벼운 사람과도 무게 제한을 초과한다면, 그보다 무거운 사람과는 당연히 함께 탈 수 없다. 따라서 이 사람은 반드시 혼자 보트를 사용해야 한다.

반대로 가장 무거운 사람과 가장 가벼운 사람의 합이 제한 이하라면, 가장 가벼운 사람을 이 사람과 묶어도 손해가 없다. 가장 가벼운 사람은 누구와도 짝을 이룰 수 있는 후보이므로, 무거운 사람과 먼저 묶어 남은 사람들의 선택 가능성을 보존할 수 있다.

그리디 선택이 안전한 이유

가장 무거운 사람을 heavy, 가장 가벼운 사람을 light라고 하자.

• heavy + light > limit이면 light보다 무거운 모든 사람과의 합도 제한을 초과한다. 따라서 heavy를 혼자 태우는 선택은 반드시 필요하다.
• heavy + light <= limit이면 heavy는 light와 함께 탈 수 있다. 다른 사람이 heavy와 짝을 이루는 해가 있더라도 light와 교체해도 두 사람 모두 제한을 넘지 않는다. 원래 light와 짝이었던 사람은 heavy보다 가벼우므로 남은 사람과 계속 처리할 수 있다.

따라서 가장 무거운 사람을 먼저 처리하고, 가능한 경우 가장 가벼운 사람과 묶는 선택은 최소 보트 수를 잃지 않는다.

오답 접근과 반례

가벼운 사람끼리 먼저 묶거나 무거운 사람끼리 먼저 묶으면 최적이 아닐 수 있다.

people = [40, 40, 60, 60]
limit = 100

무거운 사람끼리 먼저 묶으려 하면 60 + 60은 탈 수 없고, 40 + 40만 함께 탈 수 있어 보트 3개가 필요하다. 하지만 40 + 60을 두 번 묶으면 모든 사람을 보트 2개에 태울 수 있다. 가장 무거운 사람과 가장 가벼운 사람을 먼저 확인해야 하는 이유다.

시간·공간 복잡도

사람들을 정렬하는 데 O(n log n), 정렬된 배열을 양끝에서 한 번 순회하는 데 O(n)이 필요하므로 전체 시간 복잡도는 O(n log n)이다.

알고리즘은 두 포인터와 보트 수만 추가로 사용해 O(1) 공간에 동작한다. 코드가 입력 배열을 직접 정렬하므로 알고리즘 관점의 추가 공간은 O(1)이지만, Python의 정렬 구현은 내부적으로 입력 크기에 비례하는 보조 메모리를 사용할 수 있다.

3. 문제 해결 코드 (Python)

right가 가리키는 가장 무거운 사람은 매 반복에서 반드시 처리한다. 가장 가벼운 사람과 함께 탈 수 있을 때만 left를 이동하고, 무거운 사람은 항상 right를 이동한다.

def solution(people, limit):
    people.sort()

    left = 0
    right = len(people) - 1
    boats = 0

    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1

        right -= 1
        boats += 1

    return boats

두 포인터가 같은 사람을 가리키는 경우에도 보트 한 대를 사용하고 right를 줄이면 된다. left <= right 조건은 마지막으로 남은 한 사람도 처리하기 위해 필요하다. 무거운 사람을 태운 뒤에만 left를 조건부로 이동하는 것이 두 명이 함께 탔을 때와 혼자 탔을 때를 구분하는 핵심이다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 python 파일명.py로 실행하면 두 명 탑승 조건과 단독 탑승을 확인할 수 있다.

assert solution([70, 50, 80, 50], 100) == 3
assert solution([40, 40, 40], 40) == 3

4. 공식 예제와 추가 검증

작성한 solution 함수를 Python으로 실행해 공식 예제와 최소 입력, 정확히 한 보트에 탈 수 있는 경우, 그리디 선택이 필요한 경우를 확인했다.

공식 예제

추가 검증 1: 최소 입력

입력: people = [40], limit = 40
기대 출력: 1
확인 결과: 통과
검증 목적: 사람 한 명이 남은 경우에도 보트 한 대를 세는지 확인

추가 검증 2: 모든 사람이 한 보트에 탈 수 있는 경우

입력: people = [40, 40], limit = 80
기대 출력: 1
확인 결과: 통과
검증 목적: 가장 가벼운 사람과 무거운 사람을 함께 태우는 경우 확인

추가 검증 3: 무거운 사람과 가벼운 사람의 짝짓기

입력: people = [40, 50, 60, 70], limit = 100
기대 출력: 3
확인 결과: 통과
검증 목적: 가능한 짝을 먼저 만들고 남은 무거운 사람을 혼자 태우는지 확인

추가 검증 4: 무거운 사람끼리는 함께 탈 수 없는 경우

입력: people = [40, 40, 60, 60], limit = 100
기대 출력: 2
확인 결과: 통과
검증 목적: 40과 60을 짝지어 보트 수를 최소화하는지 확인

5. 다른 풀이 방식 검색 및 비교

• 프로그래머스 공식 문제는 두 사람까지 탑승할 수 있는 구명보트의 최소 개수를 구하는 조건을 정의한다.
• 프로그래머스 Python 풀이 그룹은 정렬과 투 포인터를 포함한 공개 풀이 접근을 확인할 수 있는 공식 참고 페이지다.

매번 가장 가벼운 사람부터 확인하는 방식도 생각할 수 있지만, 보트 수를 결정하는 기준은 가장 무거운 사람이 누구와 함께 탈 수 있는지다. 이 글의 방식은 가장 무거운 사람을 고정하고 가장 가벼운 사람과의 합만 확인하므로, 불필요한 조합을 만들지 않는다.

두 사람의 무게를 모두 확인하는 완전탐색은 사람 수가 많을 때 O(n^2)가 된다. 정렬 후 양끝 포인터를 사용하면 각 사람을 최대 한 번씩 이동시키면서 O(n log n)에 해결할 수 있다.

마무리

구명보트는 가장 무거운 사람을 누구와 묶을지 결정하는 그리디 문제다. 가장 가벼운 사람과도 함께 탈 수 없다면 무거운 사람은 혼자 타야 하고, 함께 탈 수 있다면 두 사람을 짝지어 보트 하나를 줄일 수 있다. 정렬과 양끝 투 포인터를 사용하면 최소 보트 수를 O(n log n) 시간에 계산할 수 있다.

관련 문제

• 숫자 게임 풀이: 정렬과 그리디 선택으로 제한된 숫자를 최적으로 매칭하는 문제