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

아이디어

• 제일 무거운애가 제일 가벼운애를 태워야한다는게 핵심 아이디어 (나는 생각 못했다)
  나는 제일 무거운애가 태울 수 있는 애들 중 제일 무거운 애를 태워야 된다고 생각했는데 반대였다. 왜냐하면 제일 무거운애가 태울 수 있는 애들 중 제일 무거운 애를 태울 수 있다면 하나 다음에 무거운애도 제일 가벼운애를 태울 수 있기 때문에 제일 가벼운애를 태우면 됨.

<예시>
[40, 60, 70, 90, 120]에서 limit이 180일 때, 
120이 60을 태울 수 있으면 90은 무조건 60을 태울 수 있기 때문에 
제일 무거운애를 안 태워도 된다.

• 두영역 풀고나서 풀었는데도 다르게 풀다가 결국 투포인터로 풀음
• 앞으로 이런문제는 투포인터가 답이다

시간복잡도

-O(N)

코드

def solution(people, limit):
    answer = 0
    n = len(people)
    people.sort(reverse=-1)
    start, end = 0, n - 1
    
    while start <= end:
        if people[start] + people[end] <= limit:
            end -= 1
		start += 1
        answer += 1
        
    return answer