[Programmers] C++ 탐욕법(Greedy)

728x90

[Programmers] C++ 탐욕법(Greedy) - 구명보트

문제 설명

보트 한 번에 최대 2명이라고 제한되어있어서 난이도가 높지 않은 문제였던 것 같다.

먼저 주어진 `vector<int> people`을 낮은 몸무게부터 오름차순으로 정렬해주었다.

다른 사람들의 풀이를 보니, 투포인터 방식으로 풀면 조금 더 깔끔하지 않았을까 싶은데

나는 조금 복잡하게(?) deque 방식으로 풀었다.

가장 낮은 몸무게, 가장 높은 몸무게 하나씩 좌우로 빼기 위해서 이 자료구조를 사용하기로 선택했다.

가장 낮은 몸무게(min)를 기준으로 삼아서, 만약 max와의 합이 `limit`을 넘지 않는다면 둘을 각각 deque에서 빼고, `answer++` 해주었다.

만약 `limit`을 넘게 된다면, min을 다시 deque에 push해서 다음 max와 비교할 수 있도록 하였다.

이와 같은 과정을 반복해서 만약 deque에 요소가 1개만 남거나 아예 empty이면 while문이 끝나도록 했다.

제한사항

무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

풀이 ( 정답 )

#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++;
            break;
        }
        int min = dq.front();
        int max = dq.back();
        dq.pop_front(); dq.pop_back();
        if(min + max <= limit) answer++;
        else {
            answer++;
            dq.push_front(min);
        }
    }
    return answer;
}

다른 사람들이 푸는 투포인터 방식으로도 풀어보았다!

풀이 ( 정답 ) - 투포인터

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int start = 0, end = people.size() - 1;
    while(start < end) {
        if(people[start] + people[end] <= limit) {
            start++;
        }
        answer++;
        end--;
        if(start == end) answer++;
    }
    return answer;
}