[Two Pointers] 프로그래머스 “구명보트” Python 풀이

문제 링크

• https://school.programmers.co.kr/learn/courses/30/lessons/42885

풀이

• 투 포인터 알고리즘을 사용해 해결할 수 있습니다.
• 구명보트에 태울 수 있는 사람은 최대 2명입니다.
• 따라서, 사람들의 몸무게를 오름차순 정렬한 뒤,
• 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나
• 한 명(몸무게가 가장 많은 사람)을 태웁니다.

코드

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