[프로그래머스] 구명보트

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

✍️ 첫번째 접근

priority_queue를 사용해서 가장 몸무게 작은 사람들순으로 보드를 태우려고 했지만 틀린 결과를 받았다. 다음과 같은 반례로 인해 보드에 [10,20], [30], [40]으로 3개의 보드를 사용하는 것이 아닌 [10,40], [20,30]으로 2개의 보드를 태울 수 있기 때문이다.
그래서, 오름차순으로 정렬하고 가장 몸무게가 작은 사람과 가장 몸무게가 큰 사람 중 limit보다 작거나 같은 경우에 보드에 태우는 것으로 접근했다. 하지만 효율성에서 시간 초과가 발생했다.

입력
[10, 20, 30, 40], 50

출력
2

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

using namespace std;

const int INF = 0x3f3f3f3f;

int solution(vector<int> people, int limit) {
    if(people.size() < 2)
        return 1;
    int answer = 0;
    sort(people.begin(),people.end());
    for(int i = 0; i < people.size(); ++i) {
        if(people[i] == INF)
            continue;
        bool flag = true;
        for(int j = people.size()-1; j >= 0; --j) {
            if(people[i]+people[j] <= limit) {
                people[i] = INF; people[j] = INF;
                ++answer;
                flag = false;
                break;
            }
        }
        if(flag)
            ++answer;
    }

    
    return answer;
}

✍️ 두번째 접근

첫번째 접근에서 2개의 for문을 사용하는데 맨 앞과 맨 뒤에서부터 시작하여 값을 계산한다? 그럼 굳이 for문을 2개 쓰지 말고, 투 포인터 개념을 적용함으로써 해결하였다.

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

using namespace std;

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