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

[Lv.2] 정답율 68%

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

프로그래머스

 

[풀이]

- greedy algorithm

- 반복문은 1번만 써야 시간 초과 실패를 하지 않는다

- pop(n) 대신 리스트[idx]를 이용해야 시간을 줄일 수 있다. pop(n)의 시간복잡도는 O(n)인 반면, list[idx] 검색의 시간 복잡도는 O(1)이기 때문이다.

- 참고로 pop, remove, insert의 시간복잡도는 모두 O(n)이다. 하지만 리스트 속 맨 마지막 요소를 삭제하는 pop()의 시간복잡도는 O(1)이다.

 

[코드]

def solution(people, limit):
    people.sort()
    count = 0
    left = 0
    right = len(people) - 1

    while left <= right :
        if left == right :
            return count + 1
        else :  
            max_person = people[right]
            if people[left] + max_person <= limit :
                left += 1
        right -= 1    
        count += 1
    return count