프로그래머스_구명보트

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

코딩테스트 연습 - 구명보트 | 프로그래머스

해당 문제는 greedy로 접근하는 문제였다.

보트 개수를 사람 수 만큼 주어준 다음 사람들의 무게를 기준으로 정렬한다.

그리고 가벼운 사람을 기준으로 함께 탈 수 있는 무거운 사람을 뒤에서부터 찾는다.

함께 탈 수 있는 경우가 있다면 보트 개수를 줄이고 다음으로 가벼운 사람과 무거운 사람을 비교한다.

이런 식으로 더 이상 비교를 할 수 없을 상황까지 갔을 때 보트 개수를 반환한다.

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

using namespace std;
bool compare(int a, int b){
    return a<b;
}
int solution(vector<int> people, int limit) {
    int answer=people.size();
    int lt = 0, hv = people.size()-1;
    sort(people.begin(), people.end(), compare);// 정렬
    
    while(lt<hv){
        // 가벼운 + 무거운 같이 탈 수 있으면
        // 보트 개수 1개 감소
        if(people[lt]+people[hv] <= limit){
            lt++, hv--, answer--;
        }
        else
            hv--;
    }
    
    return answer;
}

밑의 풀이는 처음 고려했던 단순 정렬 후 pair형 벡터에 넣는 방식이었다.

정답은 맞으나 효율성에서 통과할 수 없었다.

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

using namespace std;
bool compare(int a, int b){
    return a>b;
}
int solution(vector<int> people, int limit) {
    int answer=0;
    sort(people.begin(), people.end(), compare);// 정렬
    vector<pair<int,int>> vp; // <인원, 무게>
    
    // 하나씩 스캔 
    for(int i=0;i<people.size();i++){
        int idx = -1;
        // vp 에서 가능한 경우
        for(int j=0; idx== -1 && j<vp.size();j++){
            if(people[i] + vp[j].second <= limit)
                idx = j;
        }
        // 체크
        if(idx == -1){
            answer++;
            vp.push_back(pair<int,int>(1, people[i])); // 보트 추가
        }
        else
            vp.erase(vp.begin()+idx); // 제거
    }
    return answer;
}