[PS, Algorithm] - 구명보트 (코딩테스트 연습, LEVEL 2)

📒문제

🎈풀이

from collections import deque

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

그리디 문제치고도 꽤 간단한 문제라서 쉽게 풀 수 있을 줄 알았는데, 생각보다 시간이 걸렸다. (답 참조함 ㅠㅠ)

문제의 핵심은 1. deque 자료구조를 써야지만 효율성 테스트에서 통과할 수 있고, 2. 자료 정렬 후 limit값을 넘는 데이터부터 먼저 처리하는 것이었다.

• 코드의 아이디어는 배열을 정렬해서 맨 앞(가장 작은 무게)과 맨 뒤(가장 큰 무게)를 더해 두 사람이 limit에 걸리지 않고 한 보트에 탈 수 있는지를 판단하고 그렇지 않다면 맨 뒤의 무게를 deque에서 빼고 구명보트 개수를 하나 더해주는 방식이다.
• 이때 정렬한 맨 앞과 맨 뒤를 더해주는 이유는 가장 낮은 무게를 가진 사람이 가장 높은 무게를 가진 사람과 타야만 구명보트를 최대한 적게 쓸 수 있으며, limit에 걸릴때 deque에서 높은 무게를 가진 사람을 뺴는 이유는 이 사람은 다른 사람과 같이 탈 수 없고 구명보트를 혼자서 써야 함을 의미하기 때문이다.