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

문제

---

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

코딩테스트 연습 - 구명보트

 

 

풀이

---

def solution(people, limit):
    answer = 0
    
    people.sort() # 1
    
    left =0
    right = len(people)-1
    
    while left < right:
        if people[left] + people[right] <= limit: # 2
            left+=1
            right-=1
            answer+=1
        else: # 3
            right-=1
            answer+=1
        if left==right: # 4
            answer+=1
            break
    return answer

 

구명보트에 최대 2명씩 밖에 탈 수 없으므로 투 포인터를 사용하였다. left, right 변수를 사용하여 구해주었다.

 

people[left] : 탈출하지 않은 사람들 중에서 몸무게가 가장 가벼운 사람

people[right] : 탈출하지 않은 사람들 중에서 몸무게가 가장 무거운 사람

 

#1. 먼저 몸무게 순으로 정렬해준다.

 

#2. 가장 가벼운 사람과 가장 무거운 사람의 합이 limit 안에 들어간다면 구명보트에 두명을 태운다.

 

#3. limit 안에 들어가지 않는다면, 문제에서 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다. 라고 명시하였으므로 가장 무거운 사람을 구명보트에 태운다.

 

#4. 마지막으로 한사람만 남았을 경우 한사람만 구명보트에 태운다.