세무민의 알고가자 : 프로그래머스 구명보트 문제 풀기

오늘 풀어볼 문제는 구명보트!

---

문제 설명 

---

제한 사항 및 입출력

 

---

풀이

이번 문제는 탐욕법을 이용하는 문제에요 

말 그대로 최소보트의 개수를 구해주면 됩니다. 

예를 들어서 [70, 80, 50]을 보도록 하죠! 

limit가 100이라는 건 보트 한개에 최대 용량입니다.

보트에는 최대 2명만 탑승 가능한 경우의 수를 다 만들어보면 

70, 80, 90, 70+80, 70+50, 80+50에서 

100이하는 70, 80, 90 총 3개입니다.

따라서 최소 보트의 개수는 3개가 필요하게 됩니다.

즉 요약하자면!

1. 보트에는 최대 2명 탑승 가능하다는 조건

2. limit 이하로 탑승 가능하다는 점

3. 정렬을 하면 크기 비교가 더 쉽다.

탐욕법을 이용하게 되면 가장 빠른 접근 방법은 반복문이 되겠죠?

---

코드

def solution(people, limit):
    answer = 0
    people.sort()
    count = 0
    endPoint, startPoint = len(people) - 1, 0
    while endPoint >= startPoint:
        if people[startPoint] + people[endPoint] > limit:
            endPoint = endPoint - 1
        else:
            endPoint = endPoint - 1
            startPoint = startPoint + 1

        count = count + 1

  
    return count

코드는 간결해요! 

정렬을 해서 리스트의 크기를 순서대로 나열해준 뒤

반복문을 이용해서 startPoint, endPoint번째 사람을 합하면서 하나씩 확인해보면 됩니다. 

가장 큰값과 작은값이 리미트 값보다 크다면 endPoint를 한개씩 감소하면 되구 

해당 값보다 작다면 startPoint와 endPoint를 증가시키면 끝!

끝!

---

다음에도 알고리즘 공부 포스팅으로 찾아오겠습니다!