[c++/프로그래머스] 구명보트

문제 링크

구명보트

풀이

deque으로 푸는 문제
처음에는 이중 반복문으로 풀어서 시간 초과가 났는데, 생각해보니 그렇게 풀 이유가 없었다 ..

1. 제일 적은 몸무게와 많이 나가는 몸무게 비교를 위해 오름차순 정렬 후 deque인 dq에 넣어준다.
2. dq가 빌 때까지 반복하는데,
   2-1. de에서 제일 작은 값과 큰 값을 더했을 때 limit을 넘는다면, 큰 값은 혼자서만 구명보트를 탈 수 있으므로 answer++를 해주고, pop_back한다.
   2-2. 안 넘는다면, 그 둘이 구명보트를 타면 되니까 pop_front와 pop_back을 해준다. 물론 answer++도
   2-3. dq.size()가 1이라면 비교할 대상이 없어 런타임 에러가 뜨기 때문에 따로 예외 처리 해줌

코드

#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());
    
    deque<int> dq;
    for(int i=0;i<people.size();i++)
    {
        dq.push_back(people[i]);
    }
    
    while(!dq.empty())
    {
        if(dq.size()==1)
        {
            answer++;
            dq.pop_back();
        }
        else if(*dq.begin()+*dq.rbegin()>limit)
        {
            answer++;
            dq.pop_back();
        }
        else
        {
            answer++;
            dq.pop_front();
            dq.pop_back();
        }
    }
    
    return answer;
}