deque
으로 푸는 문제
처음에는 이중 반복문으로 풀어서 시간 초과가 났는데, 생각해보니 그렇게 풀 이유가 없었다 ..
deque
인 dq
에 넣어준다.dq
가 빌 때까지 반복하는데,de
에서 제일 작은 값과 큰 값을 더했을 때 limit
을 넘는다면, 큰 값은 혼자서만 구명보트를 탈 수 있으므로 answer++
를 해주고, pop_back
한다.pop_front
와 pop_back
을 해준다. 물론 answer++
도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;
}