https://school.programmers.co.kr/learn/courses/30/lessons/42885
문제 파악
사람들의 몸무게가 숫자형으로 주어진 people 배열과, 구명보트의 무게제한 limit 가 숫자형으로 주어진다.
구명보트에는 최대 2인까지만 탈 수 있다.
구명보트 사용의 개수를 최소화할때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 해야한다.
예시를 통해 문제를 이해해보자.
people 배열 [70, 50, 80, 50], limit 100 이 주어졌을 때,
답은 (50,50) ,(70), (80) 이렇게 최소 3개의 구명보트가 필요하여 답은 3을 return해주어야 한다.
해결 아이디어
구명보트의 타는 두 사람의 몸무게의 합이 최대한 limit의 값과 가깝되, limit를 초과해선 안된다.
people 배열을 오름차순으로 정렬한다.
[50,50,70,80]
enumerate 함수를 통해 인덱스와 몸무게를 합쳐서 튜플로 저장한다.
indexed_people = [(i, w) for i, w in enumerate(people)]
[(0,50),(1,50),(2,70),(3,80)]
.
.
로 시도했지만 막혔다.
이 문제는 몸무게가 가장 작은 사람과 큰 사람끼리 비교하고 포인터를 옮겨가며 limit에 가장 가깝되, limit 이하의 사람들끼리 짝지어주어야 하니 투포인터 기법이 적합했다.
해답 및 풀이
def solution(people, limit):
people.sort()
left = 0
right = len(people) - 1
boats = 0
# [left >> 30, 45, 50, 50, 70, 80 << right]
while left <= right:
if people[left] + people[right] <= limit: # 최소와 최대의 사람의 몸무게가 limit을 넘지 않으면, 탈출시켜주고 서로 포인터를 하나씩 옮겨준다.(탈출시키는 것은 마지막에 boats+=1로 처리)
left += 1
right -= 1
else: # 합이 limit를 넘기면, 무거운사람 한명만 탈출시킨다.
right -= 1
boats += 1
return boats
Frontend Engineers