문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42885
구명보트를 이용해 무인도에 갇힌 사람들을 구출하려고 한다. 구명보트는 최대 2명까지 탈 수 있고, 무게 제한도 있다.
예로 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이면 2/4번째 사람은 같이 탈 수 있지만 1/3번째 사람은 같이 탈 수 없다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 반환하는 함수를 작성한다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.
접근
people 배열을 내림차순으로 정렬하여 가장 무거운 사람과 가장 가벼운 사람이 함께 구명보트를 탈 수 있는지 확인한다.
people 배열에서 구명보트에 타는 사람을 제외하고 구명 보트의 수를 증가시킨다.
이 때 people 배열에서 원소를 삭제하는 방식으로 접근했는데, 값은 맞아도 효율성 조건은 만족하지 못했다.
따라서 원소를 삭제하는 방법 대신 구명보트에 탈 사람을 가리키는 변수를 사용했다.
풀이는 다음과 같다.
1. people 배열을 내림차순으로 정렬한다.
몸무게가 가장 무거운 사람과 가벼운 사람을 간단하게 찾기 위해 정렬한다.
people = sorted(people, reverse=True)
2. 구명보트에 함께 탈 몸무게가 가장 무거운 사람과 가벼운 사람을 가리키는 변수 2개를 초기화한다.
start = 0
end = len(people) - 1
3. 몸무게가 가장 무거운 사람과 가벼운 사람이 함께 구명보트에 탈 수 있는지 확인한다.
두 사람이 함께 탈 수 있으면 가장 가벼운 사람을 가리키는 변수를 다음 사람을 가리키도록 갱신한다.
구명보트에 사람이 타지 않는 경우는 없으므로 가장 무거운 사람을 가리키는 변수는 항상 다음 사람을 가리키도록 갱신하고, 필요한 구명보트의 수를 증가시킨다.
이 과정을 start, end가 같은 사람을 가리킬 때까지 반복한다.
while start <= end:
if (people[start] + people[end]) <= limit:
end -= 1
start += 1
answer += 1
전체 코드는 접은글로 처리한다.
def solution(people, limit):
people = sorted(people, reverse=True)
answer = 0
start = 0
end = len(people) - 1
while start <= end:
if (people[start] + people[end]) <= limit:
end -= 1
start += 1
answer += 1
return answer