프로그래머스 구명보트 (python, 파이썬)

• 문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

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

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

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

---

• 제한사항
  • 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
  • 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
  • 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
  • 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

---

• 입/출력

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

---

• 코드

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

    left = 0
    right = len(people)-1
    
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1
        
        answer += 1
    return answer

투포인터를 이용해서 풀면 간단하고 효율성도 통과할 수 있다.

 

간단하게 투포인터는 포인터 위치를 2개를 잡고 조건을 따져주면서 정답을 찾아주는것이다.

 

해당문제에서는 구명보트에 2명을 태워야하는데 최소한으로 구명보트를 이용해야하기 때문에 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 계속해서 매칭시켜서 최대한 한번에 태워보내주면 최소값을 찾아줄 수 있다.

 

그러기 위해서는 먼저 people의 list를 정렬을 해주어야한다. 이후 left와 right포인터 위치의 값의 합이 limit을 넘지 않으면 한번에 태워보내는 것이다. 만약 limit를 넘게 된다면 작은사람은 다른사람과 태워서 보내면 limit을 넘지 않을 수도 있기 때문에 무거운사람을 하나 태워서 보내는것이다.

 

1. 기본

[70, 50, 80, 50]

 

2. 오름차순 정렬

[50, 50, 70, 80]

 

3. 포인터 위치 변경

left	right	sum	limit	answer
0	3	130	100	1
0	2	120	100	2
0	1	100	100	3
1	0	100	100	3

---

• 출처

programmers.co.kr/learn/courses/30/lessons/42885?language=python3