[프로그래머스] 구명보트Lv.2 - Python

[프로그래머스] 구명보트Lv.2

나의 풀이

def solution(people, limit):
    people = sorted(people)
    answer = len(people)
    start = 0
    end = len(people) - 1

    while start < end:
        if people[start] + people[end] <= limit:
            start += 1
            answer -= 1
        end -= 1
    return answer

• 처음에 그리디 동전 문제처럼 그냥 오름차순 정렬해서 접근했는데 실패했다. 최대 인원 수는 2명 이였고, 양 끝을 기준으로 퀵정렬 하듯이 start와 end 위치를 조정해주면 되는 것이었다.
• 우선 people 리스트를 오름차순으로 정렬해준다.
• answer는 몸무게의 짝이 맞을 경우 1씩 빼주기 위해서 people의 길이로 잡아두었다.
• 배열을 처음과 끝 두 개의 포인트 지점에서 시작하기 위해 start = 0, end = people 길이에서 -1 을 해주었다.
• start가 end보다 작은 동안 만약 people의 start 몸무게와 end 몸무게의 합이 limit 이하라면 짝이 맞으므로 answer -= 1, start를 하나 올려준다. end은 if문과 상관없이 계속 -1을 해준다. 이 과정을 반복하다보면 start와 end가 만나는 지점이 생길 것이고 그 때 반복은 종료된다.