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

코테 다시 복습중! 11월달에 코테를 볼 수도 있어서. 감각 다시 끌어올리는 중이다.

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

프로그래머스

 

어렵게 생각할 것 없는 그리디+투포인터 문제다.

무거운 놈의 빈 자리에 가벼운 놈을 태울 수 있는가를 체크한다.
즉 무거운 애 + 가벼운 애 pair가 최솟값임은 명백하다.

투포인터를 쓰면 매우 깔끔하게 O(n)으로 해결 가능한 쉬운 문제다.

아, 배열 정렬 하고 들어가는건 잊지 말자. 그거땜에 사실 O(nlogn)이다. 

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