프로그래머스 - 구명보트

프로그래머스 - 구명보트

배열을 정렬한다면 그리디하게 풀 수 있는 문제로 배열의 앞부터 찾은 값 i와 뒤부터 찾은 값 j를 합쳐서 limit보다 작은 것이 몇 개 있는지를 체크해주는게 핵심이다.
정렬을 통해 i-1번째 값은 항상 i번째 값보다 작고, j+1번째 값은 항상 j번째 값보다 큰 것을 보장하기 때문에 i번째 값이 i-1번째 값의 선택과 상관없도록 문제의 조건에 충족하는 경우를 셀 수 있다.

나는 오름차순으로 정렬했는데, [50, 50, 70, 80]의 배열을 유지하고 뒤부터 문제에서 주어진 조건에 적합하는 경우가 있는지를 체크했는데, 이 때문에 0번째 50의 경우 80, 70, 50 순서로 체크를 해야했다.
반대로 만약 내림차순으로 정렬한다면 [80, 70, 50, 50]의 배열을 유지하고 0번째 80을 기준으로 3번째 50과 비교하여 문제에서 주어진 조건에 적합하지 않다면 바로 다음인 1번째 70으로 넘어가주면 된다.

코드는 아래와 같다.
차례대로 오름차순으로 정렬한 코드, 내림차순으로 정렬한 코드이다.
속도는 비슷해도 내림차순이 훨씬 더 깔끔하다.

#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 end = people.size();
    int last = end;
    vector<int> valid(end, 1);
    int half = limit / 2;
    for(int i=0;i<end;i++) {
        if(!valid[i])
            continue;
        answer++;
        if(people[i] > half)
            continue;

        for(int j=last-1;j>i;j--) {
            if(!valid[j])
                continue;
            if(people[i] + people[j] <= limit) {
                valid[j] = 0;
                last = j;
                break;
            }
        }
        
    }
    return answer;
}

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

using namespace std;

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