(프로그래머스) 구명보트

문제 링크

• 프로그래머스

요약

• 구명보트에 최대한 우겨넣으면 됨

최종 §

결과

• 보트에 최대한 넣으면 된다.
• 구체적으로는,
  • 우선 사람들을 무게순으로 정렬하고
  • Two pointer 를 사용한다.
    • 내림차순으로 정렬되어있고 index 0 을 l, 마지막을 r 이라고 해보자.
    • 만약 l , r 의 무게 합이 초과한다면 l 만 태워서 보낸다 (l++).
    • 만약 그렇지 안다면 둘 다 태워서 보낸다 (l++, r--).

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<int> people, int limit) {
	int l = 0;
	int r = people.size() - 1;
	int cnt = 0;
 
	sort(people.begin(), people.end(), [](auto a, auto b) {
		return a > b;
	});
 
	while (l < r) {
		if (people[l] + people[r] > limit) {
			cnt++;
			l++;
		} else {
			cnt++;
			l++;
			r--;
		}
	}
 
	return cnt + (l == r);
}

• 주의할 점은 while 의 종료조건이다.
  • 만약에 l 와 r 이 같아진다면 이놈 혼자 태워 보내면 된다.
  • 이걸 처리할 로직을 추가하기 귀찮아서, l 와 r 이 같아지지 않고 l 보다 r 이 클 때만 while 을 돌고
  • while 이 끝난 뒤에 만약 l 와 r 이 같다면 총 개수에서 1을 더하는 방식으로 했다.