[L2] 프로그래머스 구명보트 C++ 덱

리뷰

프로그래머스

 

처음엔 우선순위 큐를 두개 사용하여 min_heap, max_heap으로 구현했으나 두명 이상을 태우지 못할 때 max_heap에서부터 제거를 하다보니 max_heap이 empty상태일때 min_heap에서 그리디하게 사람을 태우지 못했다.

고민을 좀 하다가 덱을 쓰면 쉽게 문제가 풀릴 것 같아서 사용했더니 쉽게 AC를 받았다.

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. 정수형 변수 n에 people벡터의 사이즈를 저장해 주고, 정수형 덱 deq을 초기화 해준다.
2. n개의 사람 무게를 deq에 추가해 주고, deq을 오름차순으로 정렬해 준다.
3. deq이 빌때까지 반복문을 개행하고, 덱의 사이즈가 2이상이고, 시작과 끝의 합이 limit보다 작거나 같으면 덱의 앞과 뒤에서 각각 한명씩 빼내어 준다.
4. 만약 위 조건이 성립하지 않는다면 덱의 뒤에서 한명만 뽑아준다. 이후 answer을 증가시켜 준다.
5. 반복문이 종료된 후 answer에 저장된 값을 리턴해 준다.

 

참고 사항

덱을 사용하려면 데이터를 받아준 후 최초 1번 정렬을 반드시 해주어야 한다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int n = people.size();
    deque<int> deq;
    for (int i = 0; i < n; i++) deq.push_back(people[i]);
    sort(deq.begin(), deq.end());
    
    while (!deq.empty()) {
        if (deq.size() > 1 && deq.back() + deq.front() <= limit) {
            deq.pop_back();
            deq.pop_front();
        }
        else deq.pop_back();
        answer++;
    }
    
    return answer;
}