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

구명보트

첫 번째 풀이

---

• 코드 의도: 일단 생각나는대로 빨리 풀어보자
• 결과: 정확성 75점 (15/15), 효율성 15점 (3/5), 총 90점

int solution(vector<int> people, int limit)
{
    int answer = 0;

    sort(people.begin(), people.end());

    while (people.size() > 0)
    {
        int i = people.size() - 1;
        if ((i != 0) && (people[0] + people[i] <= limit))
        {
            answer++;

            people.erase(people.begin() + i);
            if (people.size() >= 1)
                people.erase(people.begin());
        }
        else
        {
            answer++;
            people.erase(people.begin() + i);
        }
    }

    return answer;
}

---

처음에는 단순히 Vector 에서 Lightest 와 Heaviest 요소를 erase 함수를 통해 지워나가면서 풀어나갔는데,
이 방법은 정확성 테스트는 모두 통과했지만, 효율성 테스트에서 1번 3번 시간 제한을 통과하지 못했다.

그 이유는 메인 루프에서 Lightest 를 제거해나갈 때 오버헤드가 발생해서인것 같다.

Vector 에서 특정 요소롤 erase 로 제거하면 해당 요소의 공간은 빈 공간이 되는데,
Vector는 순차 자료구조이기 때문에, 제거한 요소 뒤의 모든 요소들을 한 칸씩 앞으로 땡겨 재할당해준다.

내 풀이에서는 Vector 맨 앞에서 존재하는 Lightest 를 제거하는 경우가 비일비재하기에,
이 과정에서 오버헤드가 많이 발생했을 것으로 추측된다.

문제 조건에 의해 무인도에 갇힌 사람은 최대 50000명이므로, 최악의 경우, 요소들을 한 칸씩 당기는 과정을 49998번, 49996번, 49994번, … 진행하게 된다.

두 번째 풀이

---

• 코드 의도: 속도.. 속도.. 속도..!
• 결과: 정확성 75점 (15/15), 효율성 15점 (5/5), 총 100점

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

int solution(vector<int> people, int limit)
{
    int necessaryLifeBoatCount = 0;
    int count[241] = { };
    // Record Every Weight

    int first = 40;
    int end = 240;
    // First Will Be The Lightest Weight
    // End Will Be the Heaviest Weight

    for (int i = 0; i < people.size(); i++)
        count[people[i]]++;

    while (true)
    {
        if (first == end)
        {
            break;
        }

        if (count[first] == 0)
        {
            first++;
            continue;
        }

        if (count[end] == 0)
        {
            end--;
            continue;
        }

        // If The Sum Of Lightest Weight And Heaviest Weight Is Smaller Or Equals To The Limit
        // Ride Them A Boat
        if (first + end <= limit)
        {
            int temp = min(count[first], count[end]);
            count[first] -= temp;
            count[end] -= temp;
            necessaryLifeBoatCount += temp;
        }
        // If Not, The Heaviest People Can Only Ride A Boat By Themselves,
        // So Each Person With That Weight Picks Up One Boat
        else
        {
            necessaryLifeBoatCount += count[end];
            count[end] = 0;
        }
    }

    if (count[first] > 0)
    {
        if ((count[first] > 1) && (first + first <= limit))
        {
            necessaryLifeBoatCount += count[first] / 2;
            necessaryLifeBoatCount += count[first] % 2;
        }
        else
        {
            necessaryLifeBoatCount += count[first];
        }
    }

    return necessaryLifeBoatCount;
}

---

두 번째 풀이에서는 속도를 최대한 높혀보고자 했다.
실제로 이 풀이는 내 풀이 중 가장 빠른 풀이이기도 하다.

이 풀이에서는 마치 카운팅 정렬처럼,
Count 배열을 만들고, 거기에 각 인덱스를 무게 로 하는 사람 수를 저장했다.

예를 들어 Input 으로 들어온 People 이 [ 40, 50, 80, 40, 90 ] 이라면,
Count[40] 은 40KG 인 사람의 수인 2이다.

이런 Count 배열을 만들어준 이유는 두 가지가 있다.
전제는 사람의 무게가 40KG ~ 240KG으로 비교적 좁은 범위로 한정되어 있는데, 사람의 수는 1명 ~ 50,000명이나 된다는 것.

1. 때문에 같은 몸무게를 가진 사람이 많을 것이고, 이로 인해 중복되는 처리가 많을 것이라고 생각했다. 이런 중복된 처리들을 Count 배열을 이용해 한 번에 처리하고자 했다.
2. 그리고 그리디 이기 때문에 모든 요소에 접근을 해야하는데, Vector를 인덱스로 접근하는 것보다, 배열을 인덱스로 접근하는 것이 속도가 훨씬 빨랐다.

여기에 두 개의 포인터 (주소를 가리키는 포인터가 아니라 말 그대로 포인터) 를 만들었다.

Lightest: 현재 무인도에 남아있는 사람들 중 가장 가벼운 사람의 무게
Heaviest: 현재 무인도에 남아있는 사람들 중 가장 무거운 사람의 무게

Count 배열에서의 인덱스는 사람의 무게와 대응되므로,
Count[Lightest] 는 가장 가벼운 무게의 사람 수, Count[Heaviest] 는 가장 무거운 무게의 사람 수를 의미한다.

이를 이용해 메인 루프는 매 반복 마다, 아래 두 가지 작업 중 한 작업을 실행한다.

• Lightest 와 Heaviest 두 명을 보트에 태워 구출한다.
• Heaviest 한 명만 보트에 태워 구출한다.

Lightest 와 Heaviest 의 무게 합이 구명보트 무게 제한을 넘지 않으면,
Lightest 와 Heaviest 두 명을 보트에 태워보내고,

Lightest 와 Heaviest 의 무게 합이 구명보트 무게 제한을 넘지 않으면,
Heaviest 는 혼자서 밖에 보트를 탈 수 없으므로 혼자 보트에 태워 구출한다.
(가장 가벼운 Lightest 랑 짝을 지었음에도 무게 제한을 넘으므로)

최종 풀이

---

• 코드 의도: 속도.. 그리고 가독성
• 결과: 정확성 75점 (15/15), 효율성 15점 (5/5), 총 100점

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit)
{
    int boatCount = 0;
    int lightest = 0;
    int heaviest = people.size() - 1;

    sort(people.begin(), people.end());

    while (lightest <= heaviest)
    {
        if (people[lightest] + people[heaviest] <= limit)
            lightest++;

        heaviest--;
        boatCount++;
    }

    return boatCount;
}

코테 스터디 모임에서 회의를 해보니,
다른 두 팀원 분들은 모두 이런식으로 푸셨었다.

기본적인 알고리즘 자체는 기존과 비슷하고, 구현은 첫 번째 풀이와 두 번째 풀이를 섞은 것처럼 달라졌다.
이 풀이는 첫 번째 풀이처럼 Vector를 이용하되, 이번에는 요소를 지우지는 않고,
두 번째 풀이처럼 Lightest 와 Heaviest 두 개의 포인터를 이용해 현재 과정에서 처리할 요소를 결정한다.

속도는 두 번째 풀이가 훨씬 더 빠르긴 하지만, (정확성 테스트에서, 약 .01ms VS 약 .03ms)
이 풀이의 가독성이 전보다 훨씬 좋다고 생각했기에 이를 최종 풀이로 결정했다.