[알고리즘] 탐욕법(Greedy) 프로그래머스 2단계 - 구명보트

def solution(people, limit):
    
    # 1. people 배열을 정렬한다.
    people.sort()
    
    # 2. i = 배열의 첫 번째 인덱스, j = 배열의 마지막 인덱스
    i = 0
    j = len(people) - 1
    count = 0
    
    #. 3. 양 끝에서부터 i는 +1, j는 -1를 해준다.
    while i < j:
        # 3-1. 두 원소의 합이 limit 이하라면 count값을 올려주고, 위치를 옮긴다.
        if people[i] + people[j] <= limit:
            count += 1
            i += 1
            j -= 1
        # 3-2. 그렇지 않으면, j값을 줄여서 값을 작게 만든다.
        else:
            j-= 1
    
    result = len(people) - count
    return result

풀이과정

1. people 배열을 정렬한다.

2. i = 배열의 첫 번째 인덱스, j = 배열의 마지막 인덱스를 넣는다.

• 이중 for문 대신 양 끝에서부터 비교해야 효율성 좋다.

3. 양쪽 끝을 비교한다.

• i와 j의 합이 limit 이하면, count (필요한 보트)를 올려주고, 이동한다.
• i와 j의 합이 limit 초과라면, 무게를 줄여야 하기 때문에 j 값을 왼쪽으로 이동한다.