[Greedy] 42885 구명보트

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

프로그래머스

deque를 이용한 풀이

from collections import deque

def solution(people, limit):
    answer = 0
    people=deque(sorted(people)) # 가벼운 ~ 무거운
    while len(people)>=2: # 보트에 남은 사람이 2명 이상일때
        if people[0]+people[-1] <= limit:
            people.pop()
            people.popleft()
            answer+=1
        else: 
            people.pop()
            answer+=1
    if people: # 마지막으로 보트에 1명만 남아있다면 
        answer+=1

    return answer

1. people을 오름차순으로 정렬

2. people을 가장 가벼운 애 + 가장 무거운 애를 동시에 태울 수 있으면 태운다

3. 동시에 태울 수 없으면 제일 무거운 애만 태운다

4. 마지막에 한명만 남아있다면 한명을 마저 태운다

 

시간복잡도 관련..

pop(0) 의 경우 데이터를 지우고 한칸씩 앞으로 당기기 때문에 시간 복잡도는 O(1)이 아니라 O(n)임

collections.deque()를 사용하여 덱을 popleft()를 통해 시간 복잡도 문제를 해결할 수 있다

---

리스트의 index를 이용한 풀이

def solution(people, limit):
    answer = 0
    people.sort() # 몸무게 가벼운~무거운 
    left=0
    right=len(people)-1
    while left<right:
        if people[left]+people[right]<=limit: # 두 명이 한 보트를 탈때
            left+=1
            right-=1
            answer+=1
        else:
            right-=1
            answer+=1
    if left==right: # 마지막에 한명만 남게 되었다면 보트에 한명만 태움
        answer+=1

    return answer

 

---

이 문제의 핵심은 "보트에 2명을 어떤 사람으로 태울지"이다

일단 몸무게 순으로 정렬을 시킨 후,

1. 몸무게 제일 무거운 사람 2명씩 먼저 태우는 방법

2. 몸무게 제일 가벼운 사람들 2명씩 먼저 태우는 방법

3. 몸무게 제일 무거운 사람 1명+제일 가벼운 사람 1명 짝지어 먼저 태우는 방법

3가지 정도 생각해볼 수 있다

 

1번이나 2번은 둘 다 결과는 똑같을 것이다

예를 들어, limit = 100일때

몸무게 90과 80이 제일 무겁다면, 둘 다 태울 수 없을 것이다

하지만 몸무게 10이 있다면 90+10으로 동시에 두 명을 태울 수 있다

최대한 2명을 태우는 것이 중요하므로, 가장 무거운 사람과 가장 가벼운 사람의 합이 limit미만인지 check하는게 핵심이다