[코딩테스트] 프로그래머스 - 구명 보트 (Lv.2) in 파이썬 Python

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

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit이 주어짐.

 

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 할 때,

필요한 구명보트 갯수는?

 

예시: 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없다. 따라서 (1,3), (2), (4) 구성으로 보트를 타 총 세 개의 보트가 필요!

 

programmers.co.kr/learn/courses/30/lessons/42885

 

풀이

- 구명보트에 최대 2명만 탈 수 있다는 점이 문제를 단순화시켜준다.

- 사람들의 몸무게가 담겨있는 배열을 오름차순으로 정렬한다.

- 배열의 앞에서부터 출발하는 i, 끝에서부터 출발하는 j를 인덱스를 가리키는 변수로 선언.

 

- 배열의 처음 (가장 적은 몸무게)과 마지막 (가장 큰 몸무게) 원소들을 살펴보아, 그 합이 limit을 넘는 지 확인.

     - 넘는다면, 둘이 같이 보트에 타지 못한다.

          - 가장 무거운 사람 혼자 보트에 탐

          - i는 그대로, j는 하나 앞으로 (j-1) 해준다.

     - 안 넘거나 같으면, 둘이 같이 보트에 탄다.

          - i는 하나 뒤로(i+1), j는 하나 앞으로(j-1) 해준다.

 

- i와 j가 동일한 장소를 가리키거나, i가 j보다 커지면 모든 원소 탐색이 끝난 것

 

 

파이썬 구현

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

    i = 0
    j = len(people) - 1
    while i < j:
        # 최소, 최대 둘이 같이 탐
        if people[i] + people[j] <= limit:
            j -= 1
            i += 1
            answer += 1
        
        # 최대 혼자 탐
        else:
            j -=1
            answer += 1
    
    if i == j:
        answer += 1
        
    return answer