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

---

📌  풀이

이번 문제는 투 포인터를 생각하며 문제를 풀었다. 

예시 2개를 보며 문제를 파악해보자

 

 

예시 1) people = [40, 40, 40, 50, 50, 60, 70, 80], limit = 100

이 예시는 보트에 (40, 60), (40, 50), (40, 50), (70), (80) 이렇게 총 5개의 보트가 필요하다.

 

예시는 애초에 정렬이 되어 있으나 문제의 테스트 케이스는 정렬이 되어 있지 않을 수 있으므로 우선 people을 정렬해주어야 한다.

 

우선 가장 첫 번째 원소와 가장 마지막 원소의 합을 limit와 비교한다. 

40과 80을 비교해 100보다 같거나 작지 않다면 마지막 원소를 pop 해주면서 answer += 1을 해준다. 왜냐면 people은 정렬이 되어있기 때문에 가장 마지막 원소는 가장 첫 번째 원소와 같이 타지 못한다면 혼자 탈 수밖에 없기 때문에 pop을 시켜주면서 answer를 하나 늘려주는 것이다.

 

이제 가장 마지막 원소는 70이 되었다.

40과 70의 합 역시 limit인 100을 초과한다. -> 가장 마지막 원소 즉 70을 pop 시켜 주면서 answer += 1을 해준다.

 

이제 가장 마지막 원소는 60이 되었다. 

비로소 첫 번째 원소와 마지막 원소의 합이 limit와 같거나 작아졌다. 이 경우는 가장 큰 원소와 가장 작은 원소가 함께 보트를 탈 수 있으니 가장 첫 번째 원소와 마지막 원소를 함께 pop해주고 보트의 수를 하나 올려준다. 즉 answer += 1을 해준다. (이때 가장 왼쪽을 pop 해줄 때 효율적인 deque를 사용하여 시간 복잡도를 줄여준다.)

 

이제부터는 people이 정렬되어있으므로 지속하여 가장 첫번째 원소와 가장 마지막 원소가 빠져나갈 것이다. 40과 50, 40과 50이 두 번 빠져나가면 마지막으로 원소 50이 남게 된다. 이 원소 역시 같이 탈 원소가 없으니 혼자 배를 타야 하므로 마지막으로 answer += 1을 해주면 그 answer이 우리가 원하는 구명보트의 개수가 된다.

 

 

예시 2) people = [70, 80, 50], limit = 100

이 예시는 보트에 (50), (70), (80) 이렇게 모두 각각 타 3개의 보트가 필요하다.

 

우선 정렬을 해 people을 [50, 70, 80] 으로 만들어 준다.

마찬가지로 가장 첫번째와 가장 마지막 원소의 합을 limit와 비교해준다. 

합이 limit, 즉 100을 넘어가므로 마지막 원소를 pop 해준다.

이제 남은 50과 70의 합을 100과 비교한다. 

100이 더 크므로 마지막 원소 역시 pop 해준다.

이제 원소가 하나 남았으니 마지막으로 answer += 1을 해주고 return 해준다.

 

 

코드

from collections import deque
def solution(people, limit):
    answer = 0
    deq = deque(sorted(people))
    while deq:
        if len(deq) == 1:
            answer += 1
            break
        if deq[0] + deq[-1] <= limit:
            deq.pop()
            deq.popleft()
        else:
            deq.pop()
        answer += 1
    return answer