[프로그래머스 LV 2] 구명보트 C++

programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

 

보트에 최대 2명까지만 탈 수 있다는 부분을 놓쳐서 거의 2시간을 헤맸습니다... 문제를 잘 읽어야합니다..

 

카테고리는 그리디로, 우선 오름차순 정렬을 합니다.

그 후 가장 무거운(back) 에 있는 녀석과, 가장 가벼운 녀석끼리 몸무개를 합산한 후

limit 보다 작거나 같으면 둘이 슝~ 하고 보트타고 가는겁니다.

 

이렇게 둘이 갈 경우 가벼운녀석을 나타내는 인덱스값을 1올려줍니다.

 

만약 현시점 가장 가벼운녀석과 현시점 가장 무거운녀석의 몸무개 합이 limit 보다 크면 무거운녀석만 보내고

인덱스는 올리지 않습니다.

 

이런식으로 보내다보면 백터 사이즈가 점점 줄어듭니다.(무거운녀석을 pop_back 해주기때문에)

결국 백터의 사이즈보다 인덱스값이 작거나 같을 경우 반복문을 종료해주면 됩니다.

#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> people, int limit) {
    int answer = 0; int idx = 0;
    sort(people.begin(), people.end());
 
    while (people.size()>idx) {
        int back = people.back();
        people.pop_back();
        if (people[idx] + back <= limit) {
            answer++;
            idx++;
        }
        else
            answer++;
    }    
    return answer;
}

 

두시간을 헤맸는데... 2명이 최대 인승이라는걸 알았으면 이렇게... 헤매지도 않았을 문제였는데........