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

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

vector에 저장된 값을 sort 해서 deque에 넣느냐, deque에 vector의 값을 넣어서 정렬 하느냐 로 고민하다가 갓 쥐피티님께 여쭤봤다.

<chatGPT의 답변>

C++의 deque와 vector는 둘 다 시퀀스 컨테이너로, 원소를 순차적으로 저장하는 역할을 합니다. 그러나 두 컨테이너의 내부 구현 방식에 차이가 있습니다.

vector는 배열 기반의 동적 배열로 구현되어 있으며, 원소를 연속적인 메모리 공간에 저장합니다. 이로 인해 임의의 위치에 접근할 때 빠르지만, 삽입 또는 삭제 작업이 벡터의 끝이 아닌 다른 위치에서 수행될 경우 다른 원소들을 이동시켜야 하므로 비용이 높아집니다.  반면에 deque는 이중연결리스트로 구현되어 있으며, 원소들이 여러 개의 메모리 블록에 분산되어 저장됩니다. 이로 인해 임의의 위치에 접근할 때는 추가 비용이 발생하지만, 삽입 또는 삭제 작업은 상수 시간에 수행됩니다. deque는 데이터의 크기가 크거나 중간에 요소를 삽입/삭제하는 작업이 많을 때 유용합니다.  따라서, 같은 값이 포함된 경우 deque와 vector 모두 정렬에 시간이 비슷하게 소요될 것으로 예상됩니다. 정렬 알고리즘의 복잡도는 컨테이너의 내부 구현 방식과 관련이 없으며, 일반적으로 C++의 sort 함수는 퀵소트 또는 인트로소트 알고리즘을 사용하므로, 시간 복잡도는 O(n log n)입니다.

 

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    deque<int>  dq(people.begin(), people.end());
    
    sort(dq.begin(), dq.end()); // 정렬 해주고
    while (!dq.empty())
    {
        if (dq.front() + dq.back() <= limit) // 둘다 탈 수 있음
            dq.pop_front();
        if (!dq.empty())
            dq.pop_back();
        answer++;
    }
    return answer;
}