[LV2 그리디] 구명보트

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

프로그래머스

 

[풀이]

---

from collections import deque
def solution(people, limit):
    answer = 0
    people = deque(sorted(people))
    
    while len(people) >= 2:
        
        if people[0] + people[-1] > limit:
            people.pop()
            answer += 1

        else :
            answer += 1
            people.popleft()
            people.pop()
            
        if len(people) == 1:
            answer += 1
            break
            
        # print(people)
            

    
    return answer

 

최적의 해를 찾는 과정에서, 정렬을 대부분 먼저 사용합니다. 정렬을 사용할 때 파이썬 내장 sorted 메소드를 사용하면 최악의 시간복잡도는 O(n)이지만 대부분의 경우 O(nlogn)의 시간복잡도를 가집니다.

정렬 이후 deque로 리스트를 변환합니다. 풀이 아이디어는 다음과 같습니다.

[50, 50, 70, 80] <- 정렬된 deque가 있으면 해당 deque에서 제일 작은 요소, 제일 큰 요소를 더한 후 limit과 비교합니다. 가장 몸무게가 큰 사람에 가장 몸무게가 작은 사람을 태워야 구명보트를 최대한 많은 사람을 태워보낼 수 있기 때문입니다.

만약 이 둘이 limit을 넘어선다면, 몸무게가 가장 큰 사람 먼저 태워보냅니다. 이렇게 deque의 값이 2가 될 때까지 반복하다, 마지막 2가 될 때 로직을 거치고 한명이 남았다면 그 사람도 태워보냅니다.

이렇게 answer를 반환합니다.

 

[풀이 후기]

---

처음에 문제 풀이 제대로 안읽고 풀었다가, 빙 돌아갔다. 처음에는 구명보트에 작은 몸무게 가진 사람만 다 태워서 보내기 정도로만 풀었는데, 결국 구명보트를 최대한으로 이용하려면 앞 뒤를 이용해야했다. 자료구조를 이해하고 나서 풀기 쉬워진 게 많다.