[프로그래머스/Level 2] 구명보트 (C++)

programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

 

그리디가 세상에서 제일 어렵다.

 

1. 오름차순 정렬
2. idx가 0번(최소값)을 가리킨다.
3. 최소값과 최대값을 배에 넣어본다.
4. 최소값 + 최대값 <= 무게 제한 이면, 둘다 배에 타므로
   - 최소값을 가리키는 idx 1증가

5. 최대값을 제거 후, 배의 수 증가
6. idx의 값이 people 벡터의 사이즈보다 크거나 같으면 종료

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0, idx = 0;
    sort(people.begin(), people.end());
    
    while(idx < people.size()) {
        if(people[idx] + people.back() <= limit) idx++; // 최대 무게는 무조건 배에 타므로, 최소 무게만 인덱스로 비교해본다.
        people.pop_back();
        answer++;
    }

    return answer;
}

 

#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(auto it : people) {
        dq.push_back(it);
    }
    while(!dq.empty()) {
        if(dq.size() > 1 && limit - dq.back() >= dq.front()) {
            dq.pop_back();
            dq.pop_front();
        } else {
            dq.pop_back();
        }
        answer++;
    }
    return answer;
}