[프로그래머스] 구명보트 - 파이썬(python)

 

 

나의 풀이

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

• people을 오름차순으로 정렬하였다.
• 그러면, 항상 0번째 인덱스에는 몸무게가 젤 작은 사람이, 마지막 인덱스에는 몸무게가 젤 큰 사람이 위치할 것이다.
• 이때, min_index + max_index가 limit 를 초과한다면, max_index 의 사람은 누구랑도 보트를 함께 탈 수 없음을 의미하므로, 혼자서 보트를 타야한다.
• 따라서 max_index 의 값만 1 빼준다. (min_index 는 그대로)
• 마지막에, min,max_index 의 값이 같은 경우, 혼자 남은 경우이므로 answer 을 1 추가해준다.

 

+ deque 를 이용하여, popleft, pop 으로 동시에 min, max 사람을 제거하는 식으로 푼 사람들도 많았다!

그러나 count 를 하는 변수로 푸는 것이 더 간단하고 시간이 적게 걸린다!

 

+ pop() 의 경우 항상 마지막 원소를 제거하므로 O(1) 이다.

반면, del arr[i] 의 경우 O(n) 으로 시간이 많이 걸린다!!