[프로그래머스 코딩테스트 고득점 Kit / 탐욕법(Greedy)] 구명보트 (python)

풀이

def solution(people, limit):
    answer = 0
    people.sort()
    frontIdx = 0
    
    while people and frontIdx < len(people):
        leftLimit = limit
        leftLimit -= people.pop()
        
        answer += 1

        try:
            if people[frontIdx] <= leftLimit:
                leftLimit -= people[frontIdx]
                frontIdx += 1
        except IndexError:
            break
    
    return answer

내 풀이

• 문제를 푸는 핵심은 무게가 무거운 사람 + 가장 가벼운 사람(가능하다면) 조합으로 배를 태우는 것이다. 처음에는 무거운 사람 + 다음으로 무거운 사람 조합을 생각했는데 문제가 풀리지 않았다. 그리고 주의해야할 점은 배에 태울 수 있는 사람은 최대 2명이라는 것.
• 먼저 people 배열을 오름차순 정렬한다. 그리고 반복문을 돌면서 가장 무거운 사람을 pop하고 남은 무게를 다시 계산한다.
• 이때, people 배열이 비게 되거나(뒤에서부터 모두 제거된 경우), frontIdx가 현재 people 배열의 마지막 인덱스를 넘어서는 경우 반복문이 종료된다.
• 가능하다면 가벼운 사람을 한 명 더 태우는데, 처음에는 while문 안에 반복문을 하나 더 만들어 people 배열의 앞에서부터 가능한 사람을 다시 탐색했으나, 어차피 한 사람만 더 태울 수 있고 가벼운 순서대로 정렬되어 있기 때문에 이 사람이 안된다고 뒤를 더 탐색할 이유가 없다. 따라서 앞에서부터 배열을 가리키는 인덱스 변수를 하나만 만들어도 충분하기 때문에 frontIdx 변수를 이용했다.
• 무거운 사람을 pop 할 경우 배열이 비어 인덱스 에러가 발생할 수 있기 때문에 try except문으로 예외처리했고, 인덱스 에러가 발생한 경우 배열에 남아있는 사람이 없으므로 반복문을 빠져나오도록 했다.

문제는 생각보다 쉽게 풀었는데 효율성 테스트에서 애먹었다.

효율성 테스트를 통과하기 위해 시간복잡도가 O(N)인 remove와 del은 사용하지 않았고, pop으로 맨 뒤 요소만 제거했다. 그리고 앞 부분은 frontIdx 라는 변수를 따로 만들어 사용하여 시간복잡도를 O(N2)에서 O(N)으로 줄였다.