그리디가 뭔데? 투 포인터는 또 뭔데? 프로그래머스 구명보트로 알아보기

먼저 문제를 보면

1. 구명보트에는 한 번에 두 명까지만 탈 수 있고
2. 무게 합이 limit 을 넘으면 안 된다.
3. 이때 필요한 최소 보트 수를 구하라

그리디란, 매 순간 가장 최적의 선택을 해나가는 알고리즘이다. 이건 나도 알고 있다. 전체 최적해가 아니라 매 순간 "좋아 보이는 선택" 을 하는 것이다.

 

이 문제에서의 그리디 전략은 다음과 같다.

1. 제일 무거운 사람은 반드시 태운다.
2. 이 사람과 가장 가벼운 사람을 짝지을 수 있으면 최선이다.

보트 수를 최소화하려면 무거운 사람은 최대한 가벼운 사람과 함께 타야 보트의 낭비가 없기 때문이다.

 

가장 무거운 사람과 가장 가벼운 사람을 알려면 어떻게 할까? 배열을 정렬하고, 양 끝에 포인터 두 개를 둔다. 이후 조건에 따라 이동시키며 문제를 해결한다. 

정렬된 people 배열:

[i] -> 제일 가벼운 사람
[j] -> 제일 무거운 사람

 

만얃 people[i] 와 people[j] 를 더했을 때 limit 보다 작거나 같다면 둘이 함께 타는 것이 가능하다. 그러므로 둘 다 포인터를 이동한다. ( (i+=1, j -=1) 그렇지 않으면 무거운 사람 혼자 타야하기 때문에 j-=1 만 한다.

 

매 루프 마다 보트 하나씩 쓰니까 answer += 1 도 해준다.

def solution(people, limit):
    answer = 0
    people.sort()
    a = 0
    b = len(people) - 1
    while a < b :
        if people[a] + people[b] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer