Greedy - 구명보트

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

프로그래머스

이 문제를 읽고 제일 처음 들었던 생각은, 일단 'people을 정렬해야겠다.' 였다.

그리고 boat라는 이름의 deque을 만들어서, 사람을 한명씩 태우면서 limit 무게를 체크하는데,

무게가 limit을 넘어가면 limit에 맞춰서 사람을 태우고 보트의 개수를 1 증가시키는 식으로 로직을 생각했다.

 

그런데, 여기서 내가 간과했던 부분이 구명보트에는 최대 2명밖에 타지 못한다는 제한 사항이다.

그러면, 만약 limit이 120kg 이라 할때, 40kg 인 사람들은 3명이 아니라 무게를 초과하지 않아도 두 명만 한 보트에 탈 수 있는 것이다.

 

최종적으로 문제 해결은 아래 블로그를 참고했다.

https://velog.io/@daon9apples/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level-2-%EA%B5%AC%EB%AA%85%EB%B3%B4%ED%8A%B8-python

[프로그래머스 Level2] 구명보트 Python

from collections import deque

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

처음의 나는 boat라는 새로운 변수에 빈 deque을 만들었는데, 그게 아니라 정렬된 people을 deque에 담아준다. (pop과 popleft를 사용하기 위함)

그리고 이 people 이라는 deque이 비워질때까지 (모든 사람이 보트에 타서 구조될 때까지) 로직을 반복해준다.

 

만약 남은 사람이 2명 이상이라면 무게를 비교해야 하지만, 2명 이상이 아니라면 (= 1 명이라면) 혼자서 보트를 타면 되기 때문에 

무게 비교할 필요없이 구조하고(pop()으로 people에서 비워주고) answer(보트 개수)를 1 증가시켜 준다.

 

구조되지 못하고 남은 사람이 2명 이상이라면, 무게비교를 해야하는데, 우선 가장 무거운 가벼운 사람과 무거운 사람을 뽑는다.

이렇게 하는 이유는 일단 다른 사람과 동승하지 못하는 무거은 사람들은 어차피 혼자서 보트를 타야하기 때문에, 이 사람들 부터 걸러줘야

최소한의 보트를 이용할 수 있기 때문이다.

그리고 가장 무거운 사람이 누군가와 동승할 수 있다면, 그건 가장 가벼운 사람일 것이다.

 

그렇기 때문에 people[0] (가장 가벼운 사람) + people[-1] (가장 무거운 사람) 의 합이 limit 보다 작거나 같으면, 둘은 같이 한 보트에 탈 수 있다는 뜻으로 이 두 사람을 people에서 제거하고 answer를 1 증가시킨다.

만약 이 두사람의 합이 limit보다 크다면 무거운 사람은 혼자서만 보트를 탈 수 있기 때문에 무거운 사람만 people에서 제거하고 answer를 1 증가시킨다.

 

이 과정을 people이 비워질때까지 반복하면 된다.