[알고리즘] Greedy 활용 ②

지난 글(hjee02018.log - Greedy 활용 ① )에 이어 Greedy를 활용한 문제 풀이를 해보도록 한다.

1. 문제 개요

문제 출처 : 프로그래머스 구명보트 lv2

1) 문제 정의

• 배에 최대 2명을 태울 수 있으며, 태운 무게는 limit을 넘지 않도록 하는 최소 보트의 수를 구할 것

2) 제한 사항

3) 입출력 형식

2. Solution I.

1) 주요 알고리즘

① 입력으로 주어진 people 벡터를 무게 순 정렬

② 정렬된 people 벡터에서 보트에 태울 수 있는 사람들을 차례로 선택

③ 각 단계에서 선택된 두 명의 사람의 무게를 합산하여 무게 제한 limit과 비교

• w1+w2 > limit -> 1인 탑승 & answer++
• w1+w2 <= limit -> 2인 탑승 & answer++ && idx++

④ 모든 사람들이 탑승할 때까지 위 과정을 반복하며 보트의 최소 개수를 찾습니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 최대 2명 & 무게 제한
int solution(vector<int> people, int limit)
{
    int answer = 0;
    int n = people.size();
    sort(people.begin(), people.end());
    // case1. 1명 탑승
    // case2. 2명 탑승
    int i = 0;
    while (!people.empty())
    {
        if (people.size() == 1)
        {
            answer++;
            break;
        }
        int w1 = people[i];
        int w2 = people[people.size() - 1];
        // 최소 + 최대 > limit => 최대값에 해당하는 사람은 1인 탑승
        if (w1 + w2 > limit)
        {
            people.pop_back();
            answer++;
        }
        // 최소 + 최대 <limit => 2인 탑승 & people 벡터에서 제거
        else
        {
            people.erase(people.begin());
            people.pop_back();
            answer++;
        }
    }
    return answer;
}

int main()
{
    solution({70,80,50},100);
    return 0;
}

위 코드 실행 시 효율성 테스트에서 통과하지 못한다.

3. Solution II.

위 코드는 중첩반복문도 없고 n(people.size())또한 50,000이 최대값이므로 시간초과가 날 여지가 없다고 판단하였다.

한 번에 두명을 처리하도록 수정해본다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 최대 2명 & 무게 제한
int solution(vector<int> people, int limit)
{
    int answer = 0;
    int n = people.size();
    sort(people.begin(), people.end());
    // case1. 1명 탑승
    // case2. 2명 탑승
    int idx = 0;
    while (!people.empty()&&idx<people.size())
    {
        if (people.size() == 1)
        {
            answer++;
            break;
        }
        int w1 = people[idx];
        int w2 = people[people.size() - 1];
        if (w1 + w2 > limit)
        {
            people.pop_back();
            answer++;
        }
        else
        {
            people.pop_back();
            answer++;
            idx++;
        }
    }
    return answer;
}

int main()
{
    solution({ 70,80,50,50 }, 100);
    return 0;
}

위 코드의 경우 한 번에 두 명을 처리하도록 한다.
(2명 탑승하거나 1인 탑승을 2번 하거나)

• 두 코드의 정렬 부분은 동일하게 O(n log n) 이나, 그 이후의 while 루프에서의 차이점이 존재한다.
• 첫 번째 코드에서는 두 명을 처리할 때마다 맨 앞의 원소를 제거하고 맨 뒤의 원소를 제거하거나 맨 뒤의 원소만을 제거한다. 반면, 두 번째 코드에서는 두 명을 처리할 때 맨 뒤의 원소만을 제거하고 idx를 증가한다.