[프로그래머스]level2-구명보트-Python[파이썬]

문제링크

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

문제설명

알고리즘

이 문제의 핵심은 하나의 구명보트에 단 2명씩만 탈 수 있다는 것!
처음에 이 문제를 풀 때 2명 넘게 태우는 경우로 생각해서 삽질 했었다..
여튼 최대 2명씩만 태울 수 있기 때문에 문제는 훨씬 간단해진다.

그리고 몸무게가 작은 순으로 구명보트에 태운다고 무조건 정답이 되는 것이 아님!

반례 : [10, 50, 60, 70], limit : 110
작은순으로 태우게되면 (10, 50) / (60) / (70) --> 총 3개의 구명보트가 필요하게 됨.
하지만 최적의 해는 (10, 70) / (50, 60) 으로 총 2개의 구명보트가 필요하다.

--> 최적의 알고리즘
1. 몸무게 리스트 (people)을 오름차순으로 정렬한 후
2. 몸무게가 적게 나가는 사람(left)과 몸무게가 많이 나가는 사람(right)의 무게 합을 계산한다.

• 2-1. 무게 합이 limit보다 같거나 작다면
  --> 보트에 두 사람 모두 태울 수 있으므로 cnt는 1 증가하고, left는 그 다음 사람 (left += 1), right는 그 전 사람(right -= 1)을 가리키도록 값을 바꾼다.
• 2-2. 무게 합이 limit보다 크다면
  --> left는 몸무게가 더 작은 사람과 합을 구해야 하므로 right가 그 전 사람(right -=1)을 가리키도록 값을 바꾼다.

left < right 조건 하에 2번 과정을 반복하면서 2명을 태우는 보트의 개수(cnt)를 구하게 된다.

3. 남은 인원들은 모두 보트에 혼자 타게 된다. 남은 인원을 구하는 방법은
   len(people) - 2 * cnt가 된다.
   이 인원들은 보트에 혼자 타므로 2번에서 구했던 cnt값에 혼자 보트를 타는 인원을 더해주면 필요한 총 보트 개수를 구하게 된다.
   cnt += (len(people) - 2 * cnt)

코드

def solution(people, limit):
    people.sort()
    cnt = 0  
    left = 0
    right = len(people) - 1 # 2
    while left < right:            
        if people[left] + people[right] <= limit:  # left와 right 2명 모두 태울 수 있음. --> cnt 1 증가
            left += 1
            right -= 1
            cnt += 1
        else:  # right을 더 작은 값으로 이동 ex) left : 0, right : 2 -> 1 -> 0
            right -= 1
            
    cnt += (len(people) - 2 * cnt)
    return cnt