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

문제

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

구명보트에는 최대 2명밖에 탈 수 없고, 무게 제한이 있다.

 

구명보트를 최대한 적게 사용하여 사람들을 구출하려 한다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때

모든 사람을 구출하기 위해 필요한 구명보트의 개수를 반환하는 함수를 만들어야 한다.

 

 

제한조건

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

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

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

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

 

 

코드

def solution(people, limit):
    sorted_people = sorted(people)
    head = 0
    tail = len(sorted_people) - 1

    answer = 0
    while head < tail:
        if sorted_people[head] + sorted_people[tail] > limit:
            tail -= 1
            answer += 1
        else:
            head += 1
            tail -= 1
            answer += 1
    
    if head == tail:
        answer += 1

    return answer

 

 

설명

사람들의 몸무게 배열 people을 정렬해 가장 낮은 몸무게와 높은 몸무게를 가지고 비교해가면서 필요한 구명보트 개수를 찾는다.

 

sorted_people = sorted(people)
head = 0
tail = len(sorted_people) - 1

people 배열을 오름차순으로 정렬한 배열을 sorted_people이라 한다.

head와 tail은 각각 sorted_people의 첫번째 인덱스, 마지막 인덱스를 의미한다.

 

answer = 0
while head < tail:
	if sorted_people[head] + sorted_people[tail] > limit:
		tail -= 1
		answer += 1
	else:
		head += 1
		tail -= 1
		answer += 1

head가 tail보다 작을 경우에 반복한다.

가장 작은 몸무게(sorted_people[head])와 가장 큰 몸무게(sorted_people[tail])를 더해서 limit보다 클 경우

마지막을 가르키는 인덱스 tail을 1 줄이고

answer에 1을 더한다.

 

그렇지 않은 경우

head와 tail을 각각 1 더하고 빼준 뒤

answer에 1을 더한다.

 

if head == tail:
	answer += 1

위 반복이 끝난 뒤에 head와 tail이 같다면 한 명이 남았다는 의미이므로 answer에 1을 더해준다.