프로그래머스: 구명보트

문제

코딩테스트 연습 - 구명보트

 

문제 풀이

 무인도에 갇힌 사람들을 구명보트를 이용하여 탈출시키고자 할 때, 최소한의 구명보트를 구하는 문제이다. 문제의 제한 조건으로는 보트에는 최대 2명만 탑승할 수 있으며, 탑승할 수 있는 무게 제한이 있다. 따라서 사람들의 무게를 오름차순으로 정렬 후에, 큐나 이분 탐색을 통해 문제를 풀면 쉽게 해결할 수 있다.

 

큐를 이용한 풀이

• people을 정렬 후, `deque`로 변환한다.
  • list를 사용하면 `list.pop(0)`의 오버헤드가 O(N)이기 때문에 시간 초과가 발생한다.
• 가장 가벼운 사람 + 가장 무거운 사람이 보트에 탑승할 수 있는지 판단한다.
  • 무게 제한을 초과한다면, 무거운 사람을 먼저 탈출시킨다.
  • 무게 제한을 초과하지 않는다면, 제일 가벼운 사람과 제일 무거운 사람을 둘 다 탈출시킨다.
• while문을 반복할 때마다, 하나의 구명보트가 추가되는 것이다.
  • 만약 while 문을 빠져나온 후에, 사람이 남아있다면 구명보트를 추가해주어야 한다.

 

이분 탐색을 이용한 풀이

• 큐를 활용하는 방식과 마찬가지로, 무게를 오름차순으로 정렬한다.
• strart, end를 0, len(people) -1로 지정하여 가장 가벼운 사람, 가장 무거운 사람으로 지정한다.
• 큐를 반복하는 것과 마찬가지로, 2명이서 보트를 탈 수 있다면 start와 end를 모두 변경한다.
  • 이와 반대인 경우 end만 변경한다.
• 사람 수는 최대로 필요한 보트 수를 의미하므로 사람의 수 - 이분 탐색을 통해 구한 값을 하면 원하는 답을 얻을 수 있다.

 

코드

deque를 활용한 풀이

from collections import deque


def solution(people, limit):
    FIRST, LAST = 0, -1
    answer = 0
    people = deque(sorted(people))

    while len(people) > 1:
        # 가장 무거운 사람 혼자 배 타고 탈출.
        if people[FIRST] + people[LAST] > limit:
            people.pop()
        # 2명이서 배 타고 탈출.
        else:
            people.popleft()
            people.pop()
        answer += 1

    return answer + 1 if people else answer

 

이분 탐색을 활용한 풀이

def solution(people, limit):
    answer = 0
    people.sort()

    start, end = 0, len(people) - 1

    while start < end:
        if people[start] + people[end] <= limit:
            start += 1
            answer += 1
        end -= 1

    return len(people) - answer