[PS] 구명보트

구명보트

처음에 O(n^2)로 비효율적으로 풀었다.

from collections import deque

def solution(people, limit):
    people.sort()
    people = deque(people)
    stack = []
    ans = 0

    while people:
        while stack and people and stack[-1] + people[-1] > limit:
            people.pop() #혼자 타야하는 사람
            ans += 1
            
        if stack and people: #함께 탈 수 있음
            stack.pop()
            people.pop()
            ans += 1

        if people: #첫번째 대상 넣기
            stack.append(people.popleft())
            
    return ans + len(stack)

people을 정렬하고, 첫번째 원소와 마지막 원소를 짝으로 비교해서 구명보트에 같이 탈 수 있는지를 판별했다.

그런데 투포인터 방법이면, O(n)으로 끝낼 수 있다.

def solution(people, limit):
    ans = 0
    people.sort()
    
    left, right = 0, len(people)-1
    
    while left<=right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        ans += 1
        
    return ans

첫번째 풀이에서처럼 조건을 if people[left] + people[right] > limit: 이렇게 가버리면 while문을 두번 쓸 수 밖에 없다.

if people[left] + people[right] <= limit: 이렇게 조건을 가야, O(n)으로 끝낼 수 있다.