알고리즘 스터디 - 프로그래머스 : 구명보트

문제 해석

목적 : 구명보트를 적게 사용하여 사람을 구출할 수 있는 최솟값

구명보트 조건
1. 한번에 최대 2명
2. 사람들의 몸무게 people 배열
3. 무게 제한 limit 존재

어떤 알고리즘을 사용해야할까?

1. 몸무게를 내림차순으로 정렬 [80, 70, 50, 50]
2. 맨 처음 몸무게 가져옴
3. 제한 구간 내 같이 탈 수 있는 사람 중 몸무게가 가장 큰 사람을 태움

처음에 Pop을 이용하여 계산을 하였지만 효율성 테스트에서 점수를 받지 못하였다. 그래서 빼기 보다 조회를 하며 순환하는 이진 탐색 기법을 차용하여 앞 뒤가 서로 만나는 지점을 찾도록 하였다.

알고리즘 코드

def solution(people, limit):
    answer = 0
    people.sort()
    first = 0
    last = len(people) - 1
    
    while True:
        if last == first:
            answer += 1
            break
        if last < first:
            break
        
        # 2명 타는 경우
        if people[first] + people[last] <=limit:
            answer += 1
            first += 1
            last -= 1
        # 1명 타는 경우
        else:
            last -= 1
            answer += 1
    
    return answer