프로그래머스 Level 2 구명보트

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

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

처음에는 ‘완전탐색’을 이용하여 풀었으나
역시 시간초과가 발생하였다

그렇기에 생각하던 중
‘정렬’을 한다면 탐욕을 적용할 수 있다고 생각하였고
특히 정렬 이후, ‘첫 요소’와 ‘마지막 요소’의 합이 limit보다 크다면
어차피 ‘마지막 요소’는 반드시 보트에 혼자 타게 되므로
미리 답을 더해주는 방식으로 문제를 풀어 시간 내에 접근할 수 있었다

여담으로 고민은 엄청나게 오래했지만
막상 나온 코드는 깔끔하고 적은 수인 것 같아서
다시금 복잡한 기분을 느꼈다

Code

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

	int pSize = people.size();
	int lastJ = pSize - 1;

	for (int i = 0; i < lastJ; i++)
	{
		while (people[i] + people[lastJ] > limit &&
			lastJ > i)
		{
			// 어차피 정렬하였기에, 가장 작은값도 합쳐서 limit를 넘어버리면 무조건
			// 혼자서 보트 타야 하기에
			answer++;
			lastJ--;
		}

		answer++;
    // 해당 사람과 같이 타는 것이므로 마지막 인덱스를 하나 줄여준다
		if (people[i] + people[lastJ] <= limit)
			lastJ--;
	}

	return answer;
}

해결 아이디어

1. 정렬하여, 앞과 뒤의 투 포인터 방식으로 문제를 풀 수 있다
   
2. 가장 뒤 요소가 가장 큰 수이기에,
   해당 값과 ‘가장 작은 값’인 가장 앞 요소의 합이
   ‘제한’보다 크다면, ‘가장 뒤’의 요소는 반드시 보트를 혼자 타야한다
   (그렇기에 해당 시점에서 걸러준다)
   
3. 조건에 맞는 가장 뒤의 사람을 찾았다면, 추가적으로 뒤쪽의 포인터를 하나 내려준다