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

1) 문제 설명

• 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다.

 

• 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

 

• 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

 

• 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

 

• 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

2) 제한 사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.

 

• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.

 

• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.

 

• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

3) 입출력 예제

people    limit    return
[70, 50, 80, 50]    100    3
[70, 80, 50]    100    3

 

4) 입출력 예제 설명

• 없음

 

5) 풀이

from collections import deque

def solution(people, limit):

    # 정렬 (nlogn)
    people.sort()

    # Queue 생성 및 초기화 (n)
    queue = deque()
    for n in people:
        queue.append(n)

    # 구명보트 이용 횟수 (count) 및 리스트 선언
    L = []
    count = 0

    while queue:
        # 무인도에 남은 사람이 2명 이상일 경우
        if len(queue) > 1:
            min = queue.popleft()
            max = queue.pop()

            # 가장 낮은, 높은 사람 몸무게의 합이 limit보다 큰 경우
            if min + max > limit:

                # 가장 높은 사람은 혼자서 구명보트를 이용해야 하므로
                # 별도의 List에 추가하고 가장 낮은 사람 몸무게는 다시
                # Queue에 추가
                L.append(max)
                queue.appendleft(min)
            else:
                # limit보다 작으므로 count +1
                count += 1

        # 무인도에 남은 사람이 1명이므로 루프 탈출을 위해 queue에서 남은 데이터 제거하고 count +1
        else:
            queue.popleft()
            count += 1

    return count + len(L)

 

[Reference]

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

프로그래머스