탐욕법(Greedy) - 구명보트

# 효율성 만족 x  정확성은 만족 

def solution(people, limit):
    answer = 0

    people.sort()
    
    while people:
        total = people.pop(0) 
        answer += 1 
        
        if len(people) >= 1 : 
            for i in range(len(people)-1, -1, -1 ):
                if total+ people[i] <= limit : 
                    people.pop(i)
                    break     
    return answer

 

# 효율성, 정확성 둘 다 만족

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

    start = 0
    end = len(people) - 1
    while start < end :
        if people[end] + people[start] <= limit :
            start += 1
            answer += 1
        end -= 1
    return len(people) - answer

 

정렬한 다음, 작은 것과 큰 것을 묶어 태우기 위해서 투포인터를 사용한다. 

answer 에 묶어 보낼 수 있는 경우를 세서 저장한다. 

만약 가장 작은 값이랑 가장 큰 값을 더해서 limit 보다 크다면, 가장 큰 값을 하나 감소한다. 

 

list 의 remove, del 등의 연산은 index를 하나씩 수정해야 하므로 최대 O(n) 의 시간이 필요하다. 

효율성을 위해서 지우지 않고, 위와 같은 방식으로 index를 조정하여 사용하는 방법을 생각할 필요가 있다.