프로그래머스 구명보트

 

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    
    sort(people.begin(), people.end(), less<>());
    deque<int> dq;
    
    for(auto x : people) {
        dq.push_back(x);
    }
    
    while(!dq.empty()) {
                
        answer++;

        if(dq.size() == 1) {
            break;
        }
        else if(dq.front() + dq.back() > limit) {
            dq.pop_back();
        } else {
            dq.pop_back();
            dq.pop_front();
        }
    }
    
    return answer;
}

 

 

다른사람들은 어떻게 풀었나 찾아봤는데, 나는 deque를 이용해서 탐욕적으로 했고

추천수를 많이 받은 풀이는 deque를 굳이 사용하지 않고도 for 반복문 두개로 투 포인터 방식으로 풀이하셨다.

 

원리는 같았지만, 조금 더 간결한 방식이라고 생각되어 나도 해봤다.

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

using namespace std;

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