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

문제

프로그래머스 - 구명보트
🛟 문제 링크입니다! 🛟

문제 풀이

간단한 알고리즘 시나리오입니다.

1) people을 오름차순으로 정렬한다. 가벼운 사람 -> 무거운 사람
2) Two-pointer를 이용해서 (가벼운 사람 + 무거운 사람) 무게가 구명보트의 limit보다 작으면 함께 구명보트에 태운다. -> 왼쪽 pointer를 하나 오른쪽으로 이동한다.
3) 아니면 무거운 사람만 태우고 오른쪽 pointer를 하나 왼쪽으로 이동하고 구명보트 개수를 하나 증가시킨다.
4) left와 right가 같아지면 구명보트 개수를 하나 증가시키고, 총 구명보트 개수를 반환한다.

초반에 구명보트 정원이 2명이라는 문구를 흘려봐서 좀 헤맸지만, 나중에라도 캐치해서 다행이었습니다.
자기도 모르게 조건을 그냥 흘려보내는 것을 주의해야겠습니다..!

정답 처리 후 다른 분들의 답을 찾아보다가 천재적인 답안을 봤습니다.
너무 좋아서 냉큼 제 답에 추가했습니다.

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

    return len(people) - answer

마지막에 총 구명보트 개수를 구하는 부분이 천재적입니다.
이렇게 전체 인원에서 짝을 지어서 구명보트에 탄 횟수를 빼면 구명보트 개수가 간단하게 나옵니다.
연산 횟수도 확실히 줄고 보기에도 좋고 최고입니다.

이런 기발한 사고방식을 배워가는 게 알고리즘의 묘미 아닐까 싶습니다.
GOOD.

소스 코드

아래의 소스 코드 중 방법 1, 방법 2 중 하나로 하시면 됩니다.
물론 방법 2가 훨씬 더 빠릅니다.

def solution(people, limit):
    answer = 0
    left = 0
    right = len(people) - 1
    
    people.sort()
    
    # Method 1: Basic Two Pointer
    while left <= right:
        if left == right:
            answer += 1
            break
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        answer += 1
        
    return answer

    # Method 2: Using Trick!
    while left < right:
        if people[left] + people[right] <= limit:
            left += 1
            answer += 1
        right -= 1

    return len(people) - answer