프로그래머스 구명보트 CPP

구명보트

💫 첫 번째 풀이

---

• 코드 의도 : 일단 생각나는대로 빨리 풀어보자
• 결과 : 정확성 75점 (15/15), 효율성 15점 (3/5), 총 90점

int solution(vector<int> people, int limit)
{
	int answer = 0;

	sort(people.begin(), people.end());

	while (people.size() > 0)
	{
		int i = people.size() - 1;
		if ((i != 0) && (people[0] + people[i] <= limit))
		{
			answer++;

			people.erase(people.begin() + i);
			if (people.size() >= 1)
				people.erase(people.begin());
		}
		else
		{
			answer++;
			people.erase(people.begin() + i);
		}
	}

	return answer;
}

---

처음에는 단순히 Vector 에서 Lightest 와 Heaviest 요소를 erase 함수를 통해 지워나가면서 풀어나갔는데,
이 방법은 정확성 테스트는 모두 통과했지만, 효율성 테스트에서 1번 3번 시간 제한을 통과하지 못했다.

그 이유는 메인 루프에서 Lightest 를 제거해나갈 때 오버헤드가 발생해서인것 같다.

Vector 에서 특정 요소롤 erase 로 제거하면 해당 요소의 공간은 빈 공간이 되는데,
Vector는 순차 자료구조이기 때문에, 제거한 요소 뒤의 모든 요소들을 한 칸씩 앞으로 땡겨 재할당해준다.

내 풀이에서는 Vector 맨 앞에서 존재하는 Lightest 를 제거하는 경우가 비일비재하기에,
이 과정에서 오버헤드가 많이 발생했을 것으로 추측된다.

문제 조건에 의해 무인도에 갇힌 사람은 최대 50000명이므로, 최악의 경우, 요소들을 한 칸씩 당기는 과정을 49998번, 49996번, 49994번, … 진행하게 된다.

💫 두 번째 풀이

---

• 코드 의도 : 속도.. 속도.. 속도..!
• 결과 : 정확성 75점 (15/15), 효율성 15점 (5/5), 총 100점

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

int solution(vector<int> people, int limit)
{
	int necessaryLifeBoatCount = 0;
	int count[241] = { };
	// Record Every Weight

	int first = 40;
	int end = 240;
	// First Will Be The Lightest Weight
	// End Will Be the Heaviest Weight

	for (int i = 0; i < people.size(); i++)
		count[people[i]]++;

	while (true)
	{
		if (first == end)
		{
			break;
		}

		if (count[first] == 0)
		{
			first++;
			continue;
		}

		if (count[end] == 0)
		{
			end--;
			continue;
		}

		// If The Sum Of Lightest Weight And Heaviest Weight Is Smaller Or Equals To The Limit
		// Ride Them A Boat
		if (first + end <= limit)
		{
			int temp = min(count[first], count[end]);
			count[first] -= temp;
			count[end] -= temp;
			necessaryLifeBoatCount += temp;
		}
		// If Not, The Heaviest People Can Only Ride A Boat By Themselves,
		// So Each Person With That Weight Picks Up One Boat
		else
		{
			necessaryLifeBoatCount += count[end];
			count[end] = 0;
		}
	}

	if (count[first] > 0)
	{
		if ((count[first] > 1) && (first + first <= limit))
		{
			necessaryLifeBoatCount += count[first] / 2;
			necessaryLifeBoatCount += count[first] % 2;
		}
		else
		{
			necessaryLifeBoatCount += count[first];
		}
	}

	return necessaryLifeBoatCount;
}

---

두 번째 풀이에서는 속도를 최대한 높혀보고자 했다.
실제로 이 풀이는 내 풀이 중 가장 빠른 풀이이기도 하다.

이 풀이에서는 마치 카운팅 정렬처럼,
Count 배열을 만들고, 거기에 각 인덱스를 무게 로 하는 사람 수를 저장했다.

예를 들어 Input 으로 들어온 People 이 [ 40, 50, 80, 40, 90 ] 이라면,
Count[40] 은 40KG 인 사람의 수인 2이다.

이런 Count 배열을 만들어준 이유는 두 가지가 있다.
전제는 사람의 무게가 40KG ~ 240KG으로 비교적 좁은 범위로 한정되어 있는데, 사람의 수는 1명 ~ 50,000명이나 된다는 것.

1. 때문에 같은 몸무게를 가진 사람이 많을 것이고, 이로 인해 중복되는 처리가 많을 것이라고 생각했다. 이런 중복된 처리들을 Count 배열을 이용해 한 번에 처리하고자 했다.
2. 그리고 그리디 이기 때문에 모든 요소에 접근을 해야하는데, Vector를 인덱스로 접근하는 것보다, 배열을 인덱스로 접근하는 것이 속도가 훨씬 빨랐다.

여기에 두 개의 포인터 (주소를 가리키는 포인터가 아니라 말 그대로 포인터) 를 만들었다.

Lightest : 현재 무인도에 남아있는 사람들 중 가장 가벼운 사람의 무게
Heaviest : 현재 무인도에 남아있는 사람들 중 가장 무거운 사람의 무게

Count 배열에서의 인덱스는 사람의 무게와 대응되므로,
Count[Lightest] 는 가장 가벼운 무게의 사람 수, Count[Heaviest] 는 가장 무거운 무게의 사람 수를 의미한다.

이를 이용해 메인 루프는 매 반복 마다, 아래 두 가지 작업 중 한 작업을 실행한다.

• Lightest 와 Heaviest 두 명을 보트에 태워 구출한다.
• Heaviest 한 명만 보트에 태워 구출한다.

Lightest 와 Heaviest 의 무게 합이 구명보트 무게 제한을 넘지 않으면,
Lightest 와 Heaviest 두 명을 보트에 태워보내고,

Lightest 와 Heaviest 의 무게 합이 구명보트 무게 제한을 넘지 않으면,
Heaviest 는 혼자서 밖에 보트를 탈 수 없으므로 혼자 보트에 태워 구출한다.
(가장 가벼운 Lightest 랑 짝을 지었음에도 무게 제한을 넘으므로)

💫 최종 풀이

---

• 코드 의도 : 속도.. 그리고 가독성
• 결과 : 정확성 75점 (15/15), 효율성 15점 (5/5), 총 100점

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit)
{
	int boatCount = 0;
	int lightest = 0;
	int heaviest = people.size() - 1;

	sort(people.begin(), people.end());

	while (lightest <= heaviest)
	{
		if (people[lightest] + people[heaviest] <= limit)
			lightest++;

		heaviest--;
		boatCount++;
	}

	return boatCount;
}

코테 스터디 모임에서 회의를 해보니,
다른 두 팀원 분들은 모두 이런식으로 푸셨었다.

기본적인 알고리즘 자체는 기존과 비슷하고, 구현은 첫 번째 풀이와 두 번째 풀이를 섞은 것처럼 달라졌다.
이 풀이는 첫 번째 풀이처럼 Vector를 이용하되, 이번에는 요소를 지우지는 않고,
두 번째 풀이처럼 Lightest 와 Heaviest 두 개의 포인터를 이용해 현재 과정에서 처리할 요소를 결정한다.

속도는 두 번째 풀이가 훨씬 더 빠르긴 하지만, (정확성 테스트에서, 약 .01ms VS 약 .03ms)
이 풀이의 가독성이 전보다 훨씬 좋다고 생각했기에 이를 최종 풀이로 결정했다.