프로그래머스 - 구명보트

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

 

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 한다. 구명보트는 2인승에 무게제한이 있다. 최대한 적은 양의 구명보트를 사용하여 모든 사람을 구출하려고 한다.

사람들의 체중을 담은 배열 people과 구명보트의 체중 제한 limit가 주어질 때, 모든 사람을 구하기 위해 필요한 구명보트의 최솟값을 리턴하자.

 

제한 사항

• 1 <= len(people) <= 50,000
• 40 <= people[i] <= 240
• 40 <= limit <= 240
• limit는 people에 존재하는 최댓값 이상이다. 따라서 구출할 수 없는 경우는 주어지지 않는다.

 

1. 정렬 후 탐색 - O(NlogN)

문제에서 주목해야 할 조건이 하나 있다.

보트는 2인승입니다

다인승이라면 최적의 탑승 결과를 찾는데 좀 더 많은 과정이 필요하겠지만, 2인승이라면 한명을 태운 뒤, 나머지 한 명을 더 태울수 있는지만 확인하면 될 것이다.
그러면 누구를 먼저 태워보는게 좋을까?

보트에 혼자만 탈 수 있는 경우와 두 명이 탈 수 있는 경우는 무엇일까? 보트에 두 명이 탔다는 것은, 두 명의 체중의 합이 보트의 체중 제한보다 작거나 같다는 것을 의미한다. 그리고 보트에 한 명이 탔다는 것은, 남은 사람이 혼자인 경우도 있지만, 체중이 너무 많이 나가서 자신과 같이 탔을 때 체중 제한에 걸리지 않는 사람이 존재하지 않는다는 것을 의미하는 경우도 있다. 다음 경우를 살펴보자.

[40,50,100], limit = 120

입력이 위와 같이 주어졌을 때, 체중이 40인 사람과 같이 탈 수 있는 사람은 누가 있을까? 50인 사람과 같이 탈 수 있다.

그러면 체중이 100인 사람과 같이 탈 수 있는 사람은 누가 있을까? 아무도 없다. 가장 가벼운 사람인 40인 사람과 타도 체중의 총 합이 140이 되기 때문에 보트의 체중 제한 120을 초과해버린다. 따라서 100은 무조건 혼자 타야 한다.

그러면 다음과 같이 생각할 수 있다.

• 현재까지 남아있는 사람 중, 가장 무거운 사람과 가장 가벼운 사람이 함께 탈 수 없으면, 가장 무거운 사람은 혼자 타야 한다.

그러면 현재 남아있는 가장 무거운 사람과 가장 가벼운 사람을 계속해서 추적할 수 있어야 한다. 어떻게 해야 할까?

이진 트리 등을 사용하여 가장 큰 값과 가장 작은 값을 계속해서 제거해 나가는 방법도 있겠으나, 여기서는 굳이 값을 제거하지 않고, 2개의 변수를 이용하는 방법을 알아보자.

가장 먼저 해야 할 일은 배열을 정렬하는 일이다. people 배열은 정렬되어 있지 않은 배열이기 때문이다. 그러면 다음과 같은 예제가 주어졌다고 생각해보자.

[100,50,60,55,80,40], limit = 120

배열을 정렬하면 다음과 같이 될 것이다.

40	50	55	60	80	100

그리고 양 끝에 현재 남아있는 사람 중, 가장 무거운 사람과 가장 가벼운 사람을 가리키는 변수, 그리고 필요한 총 보트의 개수를 담는 변수(즉, 리턴해야 할 값)를 만들자.

left = 0, right = len(people)-1, answer = 0

이를 표로 표현하면 다음과 같이 표현할 수 있을 것이다.

40	50	55	60	80	100
l					r

그러면 people[l] + people[r]을 계산하여 남아있는 사람 중 가장 무거운 사람과 가장 가벼운 사람의 무게의 합 을 알 수 있게 된다. 계산해보면 140이 됨을 알 수 있다.
이는 남아있는 사람 중 가장 무거운 사람은 같이 탈 수 있는 사람이 없다는 것을 의미한다. 따라서 체중이 100인 사람은 혼자 타야 한다는 것을 의미한다. 그러면 l과 r의 값을 어떻게 바꿔야 할 까?

r의 값만 1 줄여주면 된다. 이러면 l은 여전히 체중이 40인 사람을 가리키고 있고, r은 100보다 다음으로 체중이 큰 사람인 80을 가리키게 된다. 그리고 필요한 보트의 수를 담은 변수 answer의 값을 1 증가시키자. 그러면 다음과 같이 될 것이다.

40	50	55	60	80	100
l				r

여기서 다시 한 번 people[l] + people[r]를 계산해보자. 이번에는 40 + 80 = 120으로 무게 제한 이하 값이 되었다. 이는 같이 타고 갈 수 있음을 의미한다. 그러면 이번에는 l과 r의 값을 어떻게 바꿔야 할 까?

r의 값을 1 줄여주는건 똑같다. 그리고 이번엔 l의 값을 1 증가시키자. 그리고 필요한 보트의 수를 담은 변수를 1 증가시키자. 그러면 다음과 같이 될 것이다.

40	50	55	60	80	100
	l		r

이번에도 people[l] + people[r]를 계산하면 limit 이하임을 알 수 있다. 따라서 다시한번 l을 1 증가시키고, r을 1 감소시킨 뒤, 필요한 보트 수를 1 증가시키면 된다.

40	50	55	60	80	100
		l,r

또 한번 people[l] + people[r]을 계산하려고 보니, l과 r이 같은 위치를 가리키고 있다. 이러면 약간 혼란이 올 수 있다. 똑같은 사람의 체중을 더해서 limit값을 확인해야 할 필요가 있나? 값을 확인하는 의미가 있나?

결론은 해도 되고 안해도 된다. 단, 실제 답에서 마지막 남은 사람의 보트를 꼭 챙겨줘야 한다는 것이다.
만약 l과 r이 동일할 때도 반복을 멈추고자 한다면, 리턴하기 전에 l과 r의 값이 동일하다면 답에 1을 더해주는 과정을 추가해야 한다.
만약 l과 r이 동일할 때도 반복을 멈추지 않는다고 하면, 그냥 내버려두면 된다. 어자피 루프 안에서 필요한 보트의 수는 1 증가하게 될 것이기 때문이다.

그러면 위의 과정은 다음과 같이 표현할 수 있을 것이다.

1. people을 정렬한 후, 양 끝을 가리키는 변수와 필요한 보트의 수를 저장하는 변수 answer를 생성한다.
   • 낮은 쪽의 인덱스를 저장하는 변수를 l, 큰 쪽의 인덱스를 저장하는 변수를 r이라고 표현한다.
2. l이 r보다 큰 곳을 가리킬 때 까지 반복한다.
   1. people[l] + people[r]값이 limit 이하라면, l의 값을 1 증가시킨다.
   2. 위의 결과와는 관계없이 r의 값을 1 감소시키고, answer의 값을 1 증가시킨다.
3. answer를 리턴한다.

 

그러면 위의 내용을 코드로 표현해보자.

 

solution.cpp

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int l=0, r=static_cast<int>(people.size())-1;
    
    sort(people.begin(), people.end());
    
    int answer = 0;    
    while (l <= r)
    {
        if (people[l] + people[r--] <= limit)
            ++l;
        ++answer;
    }
    
    return answer;
}