프로그래머스 - 구명보트 (Greedy)

 

🔸 문제 접근 방식

1. 가장 무거운 사람을 먼저 태운다.
2. 가장 가벼운 사람부터 보트에 태워나간다.
3. 보트 무게가 limit를 초과하면, 가벼운 사람을 한 명 내리고 1번으로 돌아간다.

❗ 주의 사항

처음에 리스트의 원소가 남아있을 때까지 While문을 반복하였다.

하지만 리스트 삭제 연산 수행 시 시간초과가 발생했다.

리스트 원소 최대값이 50,000임에도 비효율적인 알고리즘으로 판명되었다.

따라서 리스트를 삭제하는 대신, left, index 포인터를 두고 indexing하였다.

💧 Source Code

def solution(people, limit):
    ''' https://programmers.co.kr/learn/courses/30/lessons/42885

    Notes:
        1. 가장 무거운 사람을 먼저 태운 후 가벼운 사람을 태워 나간다.
        2. 리스트 요소를 삭제 하는 연산 대신 indexing으로 대체한다.

    Args:
        people (list): 구조할 사람의 체중(int)들이 담긴 리스트
        limit (int): 구명보트의 최대 무게

    Returns:
        cnt (int): 필요한 최소 구명보트 수
    '''

    people.sort(reverse=True)
    cnt = 0

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

    while left <= right:
        boat = people[left]
        cnt += 1
        left += 1

        while boat <= limit:
            if left > right:
                return cnt
            small = people[right]
            boat += small
            right -= 1
        right += 1

    return cnt

def worst_solution(people, limit):
    people.sort(reverse=True)
    cnt = 0

    while people:
        boat = people.pop(0)
        cnt += 1

        while boat <= limit:
            if len(people) == 0:
                return cnt
            small = people.pop()
            boat += small
        people.append(small)
    return cnt