[Python] 프로그래머스 Lv2_구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

• 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 함
• 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있음
• 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면
  • 2번째 사람과 4번째 사람은 같이 탈 수 있지만
  • 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없음
• 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 함
• 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return

제한사항

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

 

"""
입출력 예시)

people = [70, 50, 80, 50], limit = 100 -> 3
people = [70, 80, 50], limit = 100 -> 3
"""

 

 

## 의사코드 ## 

# 구명보트에 탑승할 수 있는 최대 인원수: 2
    # 1) 몸무게가 가장 가벼운 사람 + 몸무게가 가장 무거운 사람을 같이 태우기 
    # 2) 몸무게가 가장 무거운 사람 혼자 태우기

 

 

 

통과한 코드

 

def solution(people, limit):
    answer = 0
    # 몸무게가 가장 가벼운 사람부터 오름차순 정렬
    people.sort()
    # 몸무게가 가장 가벼운 사람의 인덱스, 가장 무거운 사람의 인덱스
    i, j = 0, len(people)-1

    while i <= j:
        answer += 1
        # 가장 가벼운 사람과 가장 무거운 사람을 함께 태울 수 있는 경우 
        if people[i] + people[j] <= limit:
            i += 1 # 가장 가벼운 사람의 인덱스 증가 
            j -= 1 # 가장 무거운 사람의 인덱스 감소
        # 가장 무거운 사람 혼자서만 탈 수 있는 경우 
        else:
            j -= 1

    return answer

 

 

• 가장 가벼운 사람과 가장 무거운 사람의 인덱스 활용
• 구명보트에 태울 수 있는 방법은 2가지
  • 1) 가장 가벼운 사람과 가장 무거운 사람 함께 태우기
  • 2) 가장 무거운 사람 혼자 태우기

 

• 과정 확인

people = [70, 50, 80, 50]
limit = 100

"""
몸무게가 가장 가벼운 사람: 50
몸무게가 가장 무거운 사람: 80
<가장 무거운 사람 혼자서만 탈 수 있는 경우> 

몸무게가 가장 가벼운 사람: 50
몸무게가 가장 무거운 사람: 70
<가장 무거운 사람 혼자서만 탈 수 있는 경우> 

몸무게가 가장 가벼운 사람: 50
몸무게가 가장 무거운 사람: 50
[가장 가벼운 사람과 가장 무거운 사람이 함께 탈 수 있는 경우] 

3
"""

 

 

 

 

 

참고)

 

https://wooono.tistory.com/645

[Two Pointers] 프로그래머스 “구명보트” Python 풀이