[프로그래머스] 구명보트 파이썬 풀이

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

프로그래머스

---

1. 풀이

• 구명보트는 최대 2명밖에 사용할 수 없으므로 투포인터를 활용하자

그림1

몸무게를 오름차순으로 정렬한 후 left는 가장 첫 번째 몸무게를, right는 가장 마지막 몸무게를 가리킨다.

이 두 몸무게를 합쳤을 때 limit보다 작거나 같다면 둘 다 구명 보트에 탑승하고, 아니면 right - 1해서 다시 비교하기를 반복하자. 이때 구명보트에 탑승했다면 answer + 1해주자. (answer 초기 값: 0)

 

 

• 구조 여부를 나타내는 리스트를 사용해 2명씩 구조되지 못한 사람 수를 구하자

그림2: saved 리스트

그림1에서 몸무게 70과 80은 구조되지 못 했다. 이들은 혼자서 구명보트에 타야 한다. 그 정보를 그림2 saved 리스트처럼 표현할 수 있다. 마지막에 saved 리스트에서 구조되지 않았다는 의미인 False 값의 개수를 answer에 더하면 구조에 사용된 최종 구명보트 수가 나온다.

 

 

 

2. 정답 코드

def solution(people, limit):
    left = 0
    right = len(people) - 1
    people.sort()  # 몸무게 오름차순 정렬
    saved = [False] * (right + 1)  # 구조 여부

    answer = 0
    while left < right:
        while limit < people[left] + people[right] and right > -1:
            right -= 1

        if left >= right:
            break

        saved[left] = True
        saved[right] = True
        left += 1
        right -= 1

        answer += 1

    answer += saved.count(False)
    return answer