구명보트 42885

문제

첫 번째 접근 방법

정렬해주고 앞, 뒤에서 가져오면 된다고 생각했다. (가장 큰 것과 가장 작은 것이기에)

첫 번째 실패

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit)
{
    int answer = 0;
    sort(people.begin(), people.end());
    while (!people.empty())
    {
        answer++;
        int weight = people[people.size() - 1];
        people.erase(people.begin() + (people.size() - 1));
        if (people.empty())
            break;
        int nextWeight = people[0];
        if (nextWeight + weight <= limit)
        {
            people.erase(people.begin());
        }
    }
    return answer;
}

실패했다. 정렬을 하는 것이 문제였나? 정렬은 필수라고 생각했다. 지우는 것이 문제인 것 같다.

두 번째 접근 방법

배열을 반환하는 것이 아니므로 굳이 배열을 수정하지 말고 인덱스를 돌 생각을 했다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

풀이

앞과 뒤에서 값을 찾아오게 정렬해준다.
뒤에 있는 값을 우선 확인하여 오른쪽을 감소시켜준다. 만약 앞에 있는 작은 값도 같이 사용할 수 있다면 왼쪽을 감소시켜준다.
왼쪽이 오른쪽보다 인덱스가 큰 경우면 탐색이 완료됐다는 뜻이므로 종료되게 해준다.

혹시나 했는데 진짜로 지워주는 연산 때문에 시간초과가 났다. 코드를 잘 작성하고도 잘못된 코드로 오인해서 시간을 날릴 수 있으니 앞으로는 시간이 더 걸릴만한 요소는 점검해주는 것이 좋을 것 같다.