[프로그래머스]Level.2 탐욕법(greedy) 구명보트

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

 

문제설명

제한사항

 

 

첫번쨰 풀이-효율성 실패(1번 3번)

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    int num=1;
    sort(people.begin(),people.end());

    while(1){
        int weight=limit-people.back();
        people.pop_back();
        if(weight!=0&&people.front()<=weight){
            for(int i=0;i<people.size();i++){
                if(people[i]>weight) continue;
                people.erase(people.begin()+i);
                break;
            }
        } 
        if(people.size()==0) break;
        else num++;
    }
    answer=num;
    return answer;
}

 

두번째풀이

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

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