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

 

● 소감

- 이게 왜 탐욕법인지 모르겠다.

 

● 나의 풀이

1) 문제 이해

 

- 탐욕법이라는데... 뭐 우선은 가장 가벼운 사람과 가장 무거운 사람을 비교해서 limit 안에 들어가면 보트에 태우면 되기 때문에 정렬이 필요하다고 생각했다. 정렬 후 left와 right를 증가 감소, 혹은 left만 증가 하는 식으로 비교하면 구할 수 있을 것이다.

 

2) 조건 찾기

 

- 정렬은 sort()로 간단히 할 수 있고, left는 0부터 right는 제시된 백터 people의 size의 -1 (배열순서니까)로 지정.

- 그리고 2명의 보트를 태운 경우의 변수도 만들었다.

sort(people.begin(), people.end(), greater<int>());

int left = 0;
int right = people.size() - 1;
int fullboat = 0;

 

3) 누구누구를 같이 보트에 태울까?

 

-  정렬된 왼쪽은 가장 무거운 사람, 오른쪽은 가벼운 사람이다.(greater<>() 정렬 기준). 각 인원을 더해보고 limit 보다 작거나 같다면 left와 right를 각각 증가 감소 시켜주면 되고, limit 보다 크다면 다음 무거운 사람과 더하고 비교해준다.

- 이를 left가 right의 값보다 커지거나 같아질 때까지 반복해준다.

while(left < right)
{
	if(people[left] + people[right] <= limit)
	{
		left++, right--;
		fullboat++;
	}
	else
		left++;
}

 

 

 

● 내가 작성한 답

int solution(vector<int> people, int limit)
{
	sort(people.begin(), people.end(), greater<int>());

	int left = 0;
	int right = people.size() - 1;
	int fullboat = 0;

	while(left < right)
	{
		if(people[left] + people[right] <= limit)
		{
			left++, right--;
			fullboat++;
		}
		else
			left++;
	}

	return fullboat + (people.size() - fullboat * 2);

}