JArchive 프로그래밍 일기

문제

구명보트 프로그래머스 level2

리뷰

이 문제의 핵심은 1명 또는 2명의 사람만 태울 수 있다는 것이다.

왜냐하면 제한사항이 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지기 때문이다.

맨 앞을 가리키는 인덱스 변수와 맨 뒤를 가리키는 인덱스 변수를 둔다.

그리고 people 벡터를 정렬 한다.

int front = 0; // 맨 앞 인덱스 
int back = people.size() - 1;  // 맨 뒤 인덱스 

sort(people.begin(), people.end()); // 오름차순 정렬 [50, 50, 70, 80]  

양 끝 인덱스의 사람 무게 합이 무게제한보다 작다면,

양 끝 인덱스를 증가 및 감소시킨다. (front 증가 , back 감소 )

// 인덱스 변화 :  앞에서는 증가, 뒤에서는 감소 
if (people[front] + people[back] <= limit && (back-front >= 1) ) { 
    front++; back--;  
    // 2명을 태워 보낸 셈이니까 인덱스 차이가 (back-front >= 1)  만족해야 함.
}
else { // 뒤에 큰 값만 제거 
    back--;
}

코드

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

int solution(vector<int> people, int limit) {

    int answer = 0; 
    int front = 0; // 맨 앞 인덱스 
    int back = people.size() - 1;  // 맨 뒤 인덱스 

    sort(people.begin(), people.end()); // 오름차순 정렬 

    while (front <= back) { //  양 끝 인덱스가 만날 때 까지 

        if (people[front] + people[back] <= limit && (back-front >= 1) ) {
            front++; back--;  // 인덱스 변화 :  앞에서는 증가, 뒤에서는 감소 
        }
        else { // 뒤에 큰 값만 제거 
            back--;
        }
        answer++;
    }

    return answer;
}