[Greedy] 구명보트

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

프로그래머스

 

코딩테스트를 볼 때, 가장 중요한 건 문제를 정확히 파악하는 것입니다. "구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다"라는 문구를 제대로 못 봐서 많이 헤맸습니다..

 

"구명보트" 문제는 people 리스트를 정렬한 후 최댓값과 최솟값을 더해서 limit을 초과하는지 판단 후 구명보트의 최소 개수를 구하면 됩니다.

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

people의 원소 개수가 1개라면 구명보트 수를 1증가시키고, 반복문을 종료합니다.

그렇지 않다면, people[0], people[-1]을 더한값과 limit값을 비교하여 구명보트 수를 증가시킵니다.

(limit 보다 작거나 같으면 people[0], people[-1]을 제거하고, 그렇지 않다면 people[-1]만 제거합니다.)

 

그러나 채점 결과에서 테스트1에서 시간 초과로 실패되었습니다.

 

자료구조 덱(Deque)을 이용하여, del list 대신 pop(), popleft()로 구현하면 시간 초과 문제를 해결할 수 있습니다.

시간복잡도로 보면, 리스트는 O(n)이고 덱은 O(1)이기 때문입니다.

from collections import deque

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