[Python] 구명보트 - 프로그래머스 코딩테스트

문제 설명

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

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

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

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

입출력 예시

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

제한사항

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

---

★ 문제 풀이

 

구명보트를 이용하여 무인도에서 사람들을 구출하는 문제입니다.

 

<제약 사항>

1. 보트는 한 번에 2명씩 밖에 탈 수 없다는 것

2. 무게 제한이 있다는 것

3. 구명보트를 최대한 적게 사용하려 한다는 것

 

* 최대한 무거운 사람과 최대한 가벼운 사람의 조합을 사용해

보트를 최소화하는 것에 방점을 두고 풀었습니다.

 

def solution(people, limit):
    answer = 0
    min_i = 0
    max_i = len(people)-1
    people.sort()
    cnt = 0

 

1. 사람들의 무게를 오름차순으로 정렬했구요.

 

2. 가장 가벼운 사람의 index와 가장 무거운 사람의 index를 선언해 주었습니다.

 

3. cnt는 2명이 함께 탄 보트의 개수입니다.

 

 

 while min_i < max_i:
 
        if limit >= people[min_i] + people[max_i]:
            cnt += 1
            min_i += 1
            max_i -= 1
            
        else:
            max_i -= 1

4. 가장 가벼운 사람과 가장 무거운 사람의 몸무게의 합보다 무게제한이 더 크다면,

가장 가벼운 사람과 가장 무거운 사람은 보트를 함께 타고 탈출하게 됩니다.

 

그러므로 2명이 함께 탄 보트의 개수를 의미하는 cnt를 1개 올려주고,

두 번째로 가벼운 사람과 두 번째로 무거운 사람이 함께 보트를 타고 탈출할 수 있는지 확인하기 위해 index를 하나씩 더하고 빼줍니다.

 

5. 만약 가장 가벼운 사람과 가장 무거운 사람이 무게제한에 걸려 함께 타지 못한다면,

두 번째로 무거운 사람이 가장 가벼운 사람과 함께 보트를 탈 수 있는지 확인하기 위해 max_index를 하나 빼줍니다.

 

 

  answer = len(people) - cnt
    
  return answer

6. 이렇게 확인을 이어나가다가 min_index와 max_index가 겹쳐지게 되면 반복문을 끝내고 나와서,

사람들 수에서 cnt를 빼고 return합니다. 이렇게 하는 이유는 2명이 함께 탄 보트의 개수만큼

사용 될 보트의 수가 줄어들기 때문입니다.

 

 

---

Solution 코드

def solution(people, limit):
    answer = 0
    min_i = 0
    max_i = len(people)-1
    people.sort()
    cnt = 0
    
    while min_i < max_i:
        if limit >= people[min_i] + people[max_i]:
            cnt += 1
            min_i += 1
            max_i -= 1
        else:
            max_i -= 1
    
    answer = len(people) - cnt
    
    return answer