[프로그래머스] 구명보트 / python

1️⃣ 문제 설명

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

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다.

구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

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

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때,

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return

제한사항

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

2️⃣ 풀이 전 계획과 생각

사람들을 구출할 수 없는 경우가 없음으로, 예외처리 없음

1. 초과하기 전까지, 몸무게가 작은 사람들을 순서대로 구명보트에 담자.
2. 초과하면, 다음 구명보트에 몸무게가 작은 사람들 순서대로 담자.

그러려면, 먼저 몸무게가 작은 순으로 sort해주자.

그리고 반복문을 돌려서,

초과 전까지 몸무게가 작은 사람들을 빼서 넣자.

그리고 만약에 초과하면 count += 1해주고 다시 넣자.

3️⃣ 풀이

def solution(people, limit):
    answer = 0    
    sum_weight = 0
    # 몸무게가 작은 순으로 sort
    people.sort()

    while len(people) > 0:  
        people_weight = people.pop(0)
        sum_weight += people_weight
        
        if sum_weight > limit: 
            answer += 1
            people.insert(0, people_weight)
            sum_weight = 0
    return answer

4️⃣ 1차 풀이하면서 막혔던 점과 고민

최적의 해는 몸무게가 적은 순서대로 넣는 것이 아니였다.

다른 테스트 케이스를 생각해보면,

제일 작은 사람을 넣고, 초과되지 않을 때까지, 제일 큰 순서대로 넣는 것이 최적의 해를 구할 수 있다.

5️⃣ 2차 풀이

def solution(people, limit):
    answer = 0    
    sum_weight = 0
    # 몸무게가 작은 순으로 sort
    people.sort()
    
    while len(people) > 0:
        # 가장 가벼운 친구를 pop
        sum_weight = people.pop(0)
        # 더이상 추가할 친구가 없다면, 구명보트 += 1
        if len(people) == 0:
            answer += 1
            break
        else:
            # 제일 작은 사람을 넣고, 초과되지 않을 때까지, 제일 큰 사람을 넣는다.
            is_together = False
            for i in range(len(people)-1, 1):
                if limit < = sum_weight + people[i]:
                    people.pop(i)
                    is_together = True
                    answer += 1
                    break
            # 같이 탈 사람이 없다면,  구명보트 += 1 하고 다음으로 넘어간다.
            if is_together == False:    answer += 1

6️⃣ 2차 풀이하면서 막혔던 점과 고민

투포인터로 접근해서 풀면, 반복문도 줄일 수 있다.

맨 앞, 맨 뒤 몸무게를 더하면서 limit와 비교해주고 count 증가시키자.

7️⃣ 3차 풀이 후 알게된 개념과 소감

def solution(people, limit):
    people.sort()
    count = 0
    left, right = 0, len(people) - 1
    # 투포인터 알고리즘 -> 맨 앞, 맨 뒤 몸무게를 더하면서 limit과 비교
    while left < = right:
        count += 1
        if people[left] + people[right] < = limit:
            left += 1
        right -= 1
    
    return count

• 다른 테스트 케이스도 생각해서 문제에 접근하자.
• 왼쪽과 오른쪽이 마주보는 방향은 투포인터로 접근하자. 반복문을 많이 줄일 수 있다.