구명보트

들어가는 말

얼마나 적은 보트로 사람을 옮기는지에 대한 문제다. 보트의 무게 제한이 있고 무엇보다 보트에는 최대 2명밖에 못 탄다(근데 이 최대 2명은 딱히 필요가 없는 조건이었다. 하지만 나는 이 조건을 넣어서 푸느라 시간을 잡아먹었고...).

당연히 내림차순으로 sort한 다음에 제일 큰 수부터 넣어주면 된다고 생각했다. 그래서 내림차순으로 sort를 한 다음에 이중 for문을 썼다.
첫 for문에 배열 중 가장 큰 값을 넣어주고 다음 for문에서는 나머지 값을 돌면서 남은 weight를 넣어주는 방식을 사용했다. 그러나 세 문제가 항상 틀리는 거 아닌가. 그래서 다시 문제를 보니 구명보트는 한 번에 최대 2명씩 밖에 탈 수 없다고 나와있었다. 그리고 보트의 조건을 넣었지만 여전히 틀렸다.
뭐가 문제일까? 싶었더니 다른 사람들은 deque를 이용해서 풀더라. 벡터는 원소를 복사하는 방식을 사용하지만 deque는 여러개의 메모리 블록을 할당하는 방식을 사용해 벡터보다 훨씬 빠르게 동작한다. 그래서 시간초과가 되지 않는 것이다.

코드 설명

일단 주어진 벡터를 오름차순으로 정렬한다.

오름차순으로 정렬된 벡터를 deque에 넣어준다.

다음 while문을 dq에 있는 값이 없을 때까지 돌려준다. current에 dq의 첫 값을 넣어주고 dq를 pop한다(마치 큐와 스텍 문제를 풀었을 때처럼). 그리고 limit에다가 current를 빼줘서 가능한 남은 무게인 left_w을 구해준다. 만일 dq가 비지 않고 dq의 back(제일 작은 무게)이 left_w보다 작거나 같은 경우 dq의 back을 pop한다. 그리고 answer을 ++해주면된다.
if문의 두 번째 조건은 다르게 넣어줄 수도 있다. 가능한 남은 무게를 계산하는 게 아니라 current에다가 제일 작은 수 dq.back을 더해서 이 값이 limit을 초과하는지 아닌지를 보는 것이다. 이건 다른 사람의 풀이를 참고했다.
처음에는 dq.back을 더하는 방식으로 풀었고 두 번째는 left_w을 계산하는 방식으로 풀었다.

코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    deque<int> dq;
    int current = 0;
    int left_w = 0;
    
    sort(people.begin(), people.end(), greater<int>());
    
    for(auto d : people){
        dq.push_back(d);
    }
    
    while(!dq.empty()){
        current = dq.front();
        dq.pop_front();
        left_w = limit - current;
        
        if(!dq.empty() && left_w >= dq.back()){
            dq.pop_back();
        }
        answer++;
    }
    return answer;
}